•Article•15 years ago

Дерево Фенвіка

Дерево Фенвіка – це структура даних на масиві довжини $n$ , яка дозволяє виконувати наступні операції:

Знайти значення деякої заданої функції $f$ на будь-якому відрізку $[L; R]$ за час $O (l o g_{2} n)$ ;
Змінювати значення будь-якого елементу масиву за $O (l o g_{2} n)$ ;
Вимагає $O (n)$ пам’яті, а саме стільки, скільки необхідно для зберігання масиву з $n$ елементів.

Далі в якості $f$ будемо розглядати функцію сумування.

Нехай є масив чисел $a [0... n - 1]$ . Деревом Фенвіка є масив $t [0... n - 1]$ , в кожному елементі якого зберігається сума деяких елементів масиву $a$ :

t [i] = j = F (i) \sum i a [j] = a [F (i)] + a [F (i) + 1] + ... + a [i]

де $F (i)$ – деяка функція. Від її вибору буде залежати швидкість виконання основних операцій (знаходження суми на відрізку та модифікація елементу масиву). Нас цікавить такий вибір F, при якому вказані операції будуть виконуватися за логарифмічний час $O (l o g_{2} n)$ .

Визначимо $F (x) = x & (x + 1)$ , де через '&' позначено операцію побітового "і". Розглянемо двійковий запис числа $x$ та подивимося на його молодший біт. Якщо він дорівнює $0$ , то $F (x) = x$ . Інакше число $x$ закінчується групою з однієї або декількох одиниць. Замінимо усі ці одиниці на нулі та присвоїмо отримане число значенню $F (x)$ .

Приклад 1. Приклади обчислення функції $F (x)$

$x$	Бінарне представлення числа	Бінарне представлення числа $F (x)$	$F (x)$
14	1110	1110	14
31	11111	00000	0
47	101111	100000	32
75	1001011	1001000	72

Розглянемо функцію $s u m (r)$ , яка обчислює суму елементів масиву $a$ на відрізку $[0... r]$ . Замість того щоб рухатися по усім елементам масиву $а$ , будемо рухатися по масиву $t$ , здійснюючи стрибки через відрізки там, де це можливо. Оскільки

t [r] = a [F (r)] + a [F (r) + 1] + \dots + a [r],

то

s u m (r) = (a [0] + a [1] + \dots + a [F (r) -1]) + (a [F (r)] + a [F (r) + 1] + \dots + a [r]) = = s u m (F (r) -1) + t [r] = s u m (F (F (r) -1) -1) + t [F (r) -1] + t [r] = \dots

Вказана сума розписується до тих пір, поки значення $F (\dots (F (F (r) -1) -1) \dots)$ не стане рівним нулю. Тобто $s u m (r)$ складається із сум елементів масиву а на відрізках $[F (r); r]$ , $[F (F (r) -1); F (r) -1]$ і так далі.

Значення $s u m (r)$ можна також записати у вигляді суми:

s u m (r) = t_{r_{0}} + t_{r_{1}} + t_{r_{2}} + ... + t_{r_{n}}

де $r_{0} = r, r_{i + 1} = F (r_{i}) -1 = (r_{i} & (r_{i} + 1)) -1$ .

Приклад 2. Розглянемо процес обчислення $s u m (14)$

$r_{i}$	$F (r_{i})$	$r_{i + 1} = F (r_{i}) - 1$
$14 = 111 0_{2}$	$111 0_{2} = 14$	$13$
$13 = 110 1_{2}$	$110 0_{2} = 12$	$11$
$11 = 101 1_{2}$	$100 0_{2} = 8$	$7$
$7 = 11 1_{2}$	$00 0_{2} = 0$	стоп

Із таблиці випливає, що $s u m (14) = t_{14} + t_{13} + t_{11} + t_{7}$ . Або те ж саме, що сумуються інтервали: $s u m (14) = a [14..14] + a [12..13] + a [8..11] + a [0..7]$ .

Наступний рисунок демонструє, що зберігається в масиві $t$ (дереві Фенвіка). Клітинка $i$ -го рядка та $k$ -го стовпчику чорна, якщо $a [i]$ входить до часткової суми $t_{k}$ , тобто $F (k) \leq i \leq k$ .

Аналогічно можна стверджувати, наприклад, що $a [2]$ входить в якості доданку до $t_{2}$ , $t_{3}$ , $t_{7}$ .

Приклад 3. Оскільки $F (9) = 8$ , то $t_{9} = a [8] + a [9]$ .

Так як $F (11) = 8$ , то $t_{1} 1 = a [8] + a [9] + a [10] + a [11]$ .

Для подальшого викладення матеріалу нам знадобиться функція $H (x) = x ∣ (x + 1)$ , яка замінює останній $0$ у двійковому представленні числа $x$ на $1$ . Через '|' тут позначено операцію побітового "або".

Приклад 4. В наступній таблиці наведені приклади обчислення функції $H (x)$ .

$x$	Бінарне представлення числа $x$	Бінарне представлення числа $x + 1$	$H (x)$
$14$	$1110$	$1111$	$111 1_{2} = 15$
$9$	$1001$	$1010$	$101 1_{2} = 11$
$43$	$101011$	$101100$	$10111 1_{2} = 47$
$47$	$101111$	$110000$	$11111 1_{2} = 63$
$15$	$1111$	$10000$	$1111 1_{2} = 31$

$x$	Бінарне представлення числа $x$	Бінарне представлення числа $x + 1$	$H (x)$
$16$	$10000$	$10001$	$1000 1_{2} = 17$
$21$	$10101$	$10110$	$1011 1_{2} = 23$
$31$	$11111$	$100000$	$11111 1_{2} = 63$
$60$	$111100$	$111101$	$11110 1_{2} = 61$
$1$	$1$	$10$	$1 1_{2} = 3$

Розглянемо, як за числом $i$ швидко знаходити такі числа $k$ , що $F (k) \leq i \leq k$ . Усі такі числа $k$ можна отримати з $i$ послідовними замінами самого правого (молодшого) нуля у двійковому представленні.

Приклад 5. Нехай $i = 8 = 100 0_{2}$ . Знайдемо такі $k$ , для яких $F (k) \leq i \leq k$ .

Послідовно замінюючи останній 0 у двійковому представленні $i$ на $1$ , отримаємо числа: $100 1_{2} = 9$ , $101 1_{2} = 11$ , $111 1_{2} = 15$ , $1111 1_{2} = 31$ , $11111 1_{2} = 63$ і так далі. Отже $a [8]$ буде міститися у $t_{8}, t_{9}, t_{11}, t_{15}, t_{31}, t_{63}$ і так далі.

Нехай $i = 53 = 11010 1_{2}$ . Аналогічно замінюючи послідовно по одному останньому нулю, отримуємо числа: $11011 1_{2} = 55, 11111 1_{2} = 63, 111111 1_{2} = 127$ і так далі. Отже $a [53]$ міститься у $t_{53}, t_{55}, t_{63}, t_{127}$ і так далі.

Для збільшення значення $a [i]$ на $d e lt a$ необхідно додати $d e lt a$ до усіх $t_{k}$ , в які входить $a [i]$ в якості доданку. Наприклад, для збільшення $a [8]$ на $1$ , необхідно додати $1$ до $t_{8}, t_{9}, t_{11}, t_{15}, t_{31}, \dots$ .

Таким чином, для виконання операції $a [i] = a [i] + d e lt a$ необхідно додати $d e lt a$ до

t_{k_{0}}, t_{k_{1}}, t_{k_{2}}, t_{k_{3}}, ..., t_{k_{n}}

де $k_{0} = i$ , $k_{j_{+} 1} = H (k_{j}) = k_{j} ∣ (k_{j} + 1)$ . Цикл додавання $d e lt a$ завершується як тільки $k_{p + 1}$ стане більшим за $n - 1$ .

Приклад 6. Нехай є масив чисел $а$ довжини $n = 100$ (комірки масиву пронумеровані від $0$ до $99$ ). Необхідно додати одиницю до $a [17]$ . Які елементи масиву $t$ необхідно збільшити на одиницю?

Діючи таким же чином, як і у прикладі 5, запишемо число $17$ у двійковому коді: $17 = 1000 1_{2}$ , тобто $k_{0} = 17$ , і першим значенням, яке слід збільшити на $1$ , буде $t_{1} 7$ . Інші кроки алгоритму подані у в таблиці:

$j$	$k_{j}$	$k_{j + 1} = H (k_{j}) = k_{j} ∣ (k_{j} + 1)$	значення що збільшується
$0$	$41 = 10100 1_{2}$	$43 = 10101 1_{2}$	$t_{41}$
$1$	$43 = 10101 1_{2}$	$47 = 10111 1_{2}$	$t_{43}$
$2$	$47 = 10111 1_{2}$	$63 = 11111 1_{2}$	$t_{47}$
$3$	$63 = 11111 1_{2}$	$127 = 111111 1_{2}$	$t_{63}$
$4$	$127 = 111111 1_{2}$	$255 = 1111111 1_{2}$	$t_{127}$
$5$	$255 = 1111111 1_{2}$	зупинка, оскільки $k_{5} = 255 > 149 = n -1$

Далі представлені функції, які працюють з деревом Фенвіка.

vector<int> t;
int n;

// ініціализація масиву t - дерева Фенвіка
void init (int nn) {
    n = nn;
    t.assign (n, 0);
}

// a[0] + a[1] + ... + a[r]
int sum (int r) {
    int result = 0;
    for (; r >= 0; r = (r & (r+1)) - 1)
        result += t\[r\];

    return result;
}

// a[i] = a[i] + delta
void inc (int i, int delta) {
    for (; i < n; i = (i | (i+1)))
        t[i] += delta;
}

// a[l] + a[l+1] + ... + a[r]
int sum (int l, int r) {
    return sum (r) - sum (l-1);
}

Список літератури

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server

$r_{i}$	$F (r_{i})$	$r_{i + 1} = F (r_{i}) - 1$
$43 = 101011 1_{2}$	$10100 0_{2} = 40$	$39$
$39 = 10011 1_{2}$	$10000 0_{2} = 32$	$31$
$31 = 1111 1_{2}$	$0000 0_{2} = 0$	стоп

$r_{i}$	$F (r_{i})$	$r_{i + 1} = F (r_{i}) - 1$
$5 = 10 1_{2}$	$10 0_{2} = 4$	$3$
$3 = 1 1_{2}$	$0 0_{2} = 0$	стоп