microbik.ru
1

ДЕРЕВО ФЕНВІКА


У статті розглядається структура даних, яка дозволяє знаходити суму сусідніх елементів масиву, а також модифікувати їх за логарифмічний час. Таку структуру називають суматором, у статті вона реалізована за допомогою дерева Фенвіка.


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

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

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

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


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


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

= a[F(i)] + a[F(i) + 1] + … + a[i],

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


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


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


x

бінарне представлення числа x

бінарне представлення числа F(x)

F(x)

14

1110

1110

14

31

11111

00000

0

47

101111

100000

32

75

1001011

1001000

72


Вправа 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) можна також записати у вигляді суми:

sum(r) = ,

де r0 = r, ri+1 = F(ri) – 1 = (ri & (ri + 1)) – 1.


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


ri

F(ri)

ri+1 = F(ri) – 1

14 = 11102

11102 = 14

13

13 = 11012

11002 = 12

11

11 = 10112

10002 = 8

7

7 = 1112

0002 = 0

зупинка


Із таблиці випливає, що sum(14) = t14 + t13 + t11 + t7. Або те ж саме, що сумуються інтервали: 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] входить до часткової суми tk, тобто .



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


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

Оскільки F(11) = 8, то t11 = a[8] + a[9] + a[10] + a[11].


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

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


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


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


x

бінарне представлення числа x

бінарне представлення числа x + 1

H(x)

14

1110

1111

11112 = 15

9

1001

1010

10112 = 11

43

101011

101100

1011112 = 47

47

101111

110000

1111112 = 63

15

1111

10000

111112 = 31


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

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


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


Приклад 5. Нехай i = 8 = 10002. Знайдемо такі k, для яких .

Послідовно замінюючи останній 0 у двійковому представленні i на 1, отримаємо числа: 10012 = 9, 10112 = 11, 11112 = 15, 111112 = 31, 1111112 = 63 і так далі. Отже a[8] буде міститися у t8, t9, t11, t15, t31 t63 і так далі.

Нехай i = 53 = 1101012. Аналогічно замінюючи послідовно по одному останньому нулю, отримуємо числа: 1101112 = 55, 1111112 = 63, 11111112 = 127 і так далі. Отже a[53] міститься у t53, t55, t63, t127 і так далі.


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

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


Для збільшення значення a[i] на delta необхідно додати delta до усіх tk, в які входить a[i] в якості доданку. Наприклад, для збільшення a[8] на 1, необхідно додати 1 до t8, t9, t11, t15, t31, … .


Таким чином, для виконання операції a[i] = a[i] + delta необхідно додати delta до , де k0 = i, kj+1 = H(kj) = kj | (kj + 1). Цикл додавання delta завершується як тільки kp+1 стане більшим за n – 1.


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

Діючи таким же чином, як і у прикладі 5, запишемо число 17 у двійковому коді: 17 = 100012, тобто k0 = 17, і першим значенням, яке слід збільшити на 1, буде t17. Інші кроки алгоритму подані у в таблиці:


j

kj

kj+1 = H(kj) = kj | (kj + 1)

значення що збільшується

0

17 = 100012

19 = 100112

t17

1

19 = 100112

23 = 101112

t19

2

23 = 101112

31 = 111112

t23

3

31 = 111112

63 = 1111112

t31

4

63 = 1111112

127 = 11111112

t63

5

127 = 11111112

зупинка, оскільки k5 = 127 > 99 = n – 1


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


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


vector 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.

ri

F(ri)

ri+1 = F(ri) – 1

5 = 1012

1002 = 4

3

3 = 112

002 = 0

зупинка

sum(5) = t5 + t3. Або sum(5) = a[4..5] + a[0..3].


b) x = 11.

ri

F(ri)

ri+1 = F(ri) – 1

11 = 10112

10002 = 8

7

7 = 1112

0002 = 0

зупинка

sum(11) = t11 + t7. Або sum(11) = a[8..11] + a[0..7].


c) x = 43.

ri

F(ri)

ri+1 = F(ri) – 1

43 = 1010112

1010002 = 40

39

39 = 1001112

1000002 = 32

31

31 = 111112

000002 = 0

зупинка

sum(43) = t43 + t39 + t31. Або sum(43) = a[40..43] + a[32..39] + a[0..31].


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

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

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

d) F(50) = 50, тому t50 = a[50].


4.

x

бінарне представлення числа x

бінарне представлення числа x + 1

H(x)

16

10000

10001

100012 = 17

21

10101

10110

101112 = 23

31

11111

100000

1111112 = 63

60

111100

111101

1111012 = 61

1

1

10

112 = 3


5. a) i = 4 = 1002: 1012 = 5, 1112 = 7, 11112 = 15, 111112 = 31 і так далі.

a[4] міститься в t4, t5, t7, t15, t31 і так далі.


b) i = 11 = 10112: 11112 = 15, 111112 = 31 і так далі.

a[11] міститься в t11, t15, t31 і так далі.


c) i = 25 = 110012: 110112 = 27, 111112 = 31 і так далі.

a[25] міститься в t25, t27, t31 і так далі.


6.

j

kj

kj+1 = H(kj) = kj | (kj + 1)

значення що збільшується

0

41 = 1010012

43 = 1010112

t41

1

43 = 1010112

47 = 1011112

t43

2

47 = 1011112

63 = 1111112

t47

3

63 = 1111112

127 = 11111112

t63

4

127 = 11111112

255 = 111111112

t127

5

255 = 111111112

зупинка, оскільки k5 = 255 > 149 = n – 1