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

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

   1. Знайти значення деякої заданої функції f на будь-якому відрізку [L; R] за час O(log₂n);

   2. Змінювати значення будь-якого елементу масиву за O(log₂n);

   3. Вимагає O(n) пам’яті, а саме стільки, скільки необхідно для зберігання масиву з n елементів.

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

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

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

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

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

   Вправа 1. Обчислити F(x), де

a) x = 16;   b) x = 19;    c) x = 25;    d) x = 119;   e) x = 127;

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

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

   то

sum(r) = (a[0]  + a[1] + … + a[F(r) – 1]) + (a[F(r)] + a[F(r) + 1] + … + a[r]) =

= sum(F(r) – 1) + t[r] =

sum(F(F(r) – 1) – 1) + t[F(r) – 1] + t[r] = …

   Вказана сума розписується до тих пір, поки значення F(…(F(F(r) – 1) – 1) …) не стане рівним нулю. Тобто sum(r) складається із сум елементів масиву а на відрізках [F(r); r], [F(F(r) – 1); F(r) – 1] і так далі.

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

   де r₀ = r, r_i+1 = F(r_i) – 1 = (r_i & (r_i + 1)) – 1.

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

   Із таблиці випливає, що sum(14) = t₁₄ + t₁₃ + t₁₁ + t₇. Або те ж саме, що сумуються інтервали: sum(14) = a[14..14] + a[12..13] + a[8..11] + a[0..7].

   Вправа 2. Розписати значення sum(x) у вигляді суми

де

a) x = 5;    b) x = 11;    c) x = 43;

   Представити sum(x) у вигляді суми інтервалів масиву а як показано у прикладі 2.

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

   Аналогічно можна стверджувати, наприклад, що a[2] входить в якості доданку до t₂, t₃, t₇.

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

   Так як F(11) = 8, то t₁₁ = a[8] + a[9] + a[10] + a[11].

   Вправа 3. Представити значення t_x у вигляді суми елементів масиву а, якщо

a) x = 15;    b) x = 21;    c) x = 47;    d) x = 50;

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

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

   Вправа 4. Обчислити H(x), де

a) x = 16;   b) x = 21;    c) x = 31;    d) x = 60;   e) x = 1;

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

   Приклад 5. Нехай i = 8 = 1000₂. Знайдемо такі k, для яких F(k) ≤ i ≤ k.

   Послідовно замінюючи останній 0 у двійковому представленні i на 1, отримаємо числа: 1001₂ = 9,  1011₂ = 11, 1111₂ = 15, 11111₂ = 31, 111111₂ = 63  і так далі. Отже a[8] буде міститися у t₈, t₉, t₁₁, t₁₅, t₃₁t₆₃ і так далі.

   Нехай i = 53 = 110101₂. Аналогічно замінюючи послідовно по одному останньому нулю, отримуємо числа: 110111₂ = 55,  111111₂ = 63, 1111111₂ = 127  і так далі. Отже a[53] міститься у t₅₃, t₅₅, t₆₃, t₁₂₇ і так далі.

   Вправа 5. Для кожного із наступних значень i знайти такі k, для яких F(k) ≤ i ≤ k:

a) i = 4;    b) i = 11;    c) i = 25;

   Для збільшення значення a[i] на delta необхідно додати delta до усіх t_k, в які входить a[i] в якості доданку. Наприклад, для збільшення a[8] на 1, необхідно додати 1 до t₈, t₉, t₁₁, t₁₅, t₃₁, … .

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

де k₀ = i, k_j+1 = H(k_j) = k_j | (k_j + 1). Цикл додавання delta завершується як тільки k_p+1 стане більшим за n – 1.

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

   Діючи таким же чином, як і у прикладі 5, запишемо число 17 у двійковому коді: 17 = 10001₂, тобто k₀ = 17, і першим значенням, яке слід збільшити на 1, буде t₁₇. Інші кроки алгоритму подані у в таблиці:

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

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

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);

}

СПИСОК ЛІТЕРАТУРИ

1. http://corum.mephist.ru/index.php?showtopic=17160
2. http://e-maxx.ru/algo/fenwick_tree
3. http://informatics.mccme.ru/moodle/mod/book/view.php?id=491

ВІДПОВІДІ ДО ВПРАВ

   1.a) 16, b) 16, c) 24, d) 112, e) 0.

   2.a) x = 5.

   sum(5) = t₅ + t₃. Або sum(5) = a[4..5] + a[0..3].

   b) x = 11.

   sum(11) = t₁₁ + t₇. Або sum(11) = a[8..11] + a[0..7].

   c) x = 43.

   sum(43) = t₄₃ + t₃₉ + t₃₁. Або sum(43) = a[40..43] + a[32..39] + a[0..31].

   3. a) F(15) = 0, тому t₁₅ = a[0] + a[1] + … + a[14] + a[15].

   b) F(21) = 20, тому t₂₁ = a[20] + a[21].

   c) F(47) = 32, тому t₄₇ = a[32] + a[33] + … + a[46] + a[47].

   d) F(50) = 50, тому t₅₀ = a[50].

4.

5.a) i = 4 = 100₂: 101₂ = 5, 111₂ = 7, 1111₂ = 15, 11111₂ = 31 і так далі.

        a[4] міститься в t₄, t₅, t₇, t₁₅, t₃₁ і так далі.

    b) i = 11 = 1011₂: 1111₂ = 15, 11111₂ = 31 і так далі.

        a[11] міститься в t₁₁, t₁₅, t₃₁ і так далі.

    c) i = 25 = 11001₂: 11011₂ = 27, 11111₂ = 31 і так далі.

        a[25] міститься в t₂₅, t₂₇, t₃₁ і так далі.

6.