Дерево Фенвіка: як зберігати й оновлювати суми

Дерево Фенвіка корисне в задачах, де числа в масиві змінюються, а суми потрібно рахувати багато разів.

Візьмемо вісім чисел:

3 1 4 1 5 9 2 6

Нехай потрібно виконувати дві операції:

• додати число до одного елемента;
• знайти суму від початку масиву до вибраної позиції.

Звичайний цикл легко знайде суму. Але для сьомої позиції він прочитає сім елементів. Якщо масив містить сотні тисяч чисел і таких запитів багато, постійний перебір стає дорогим.

Можна заздалегідь порахувати всі накопичені суми:

3 4 8 9 14 23 25 31

Тоді сума перших семи чисел одразу дорівнює 25.

Але після зміни третього числа доведеться виправити суми для третьої, четвертої, п’ятої та всіх наступних позицій. Швидке читання отримали, зате оновлення стало повільним.

Дерево Фенвіка зберігає не всі накопичені суми, а суми окремих блоків. Для восьми позицій вони виглядають так:

позиція 1 зберігає суму [1]
позиція 2 зберігає суму [1–2]
позиція 3 зберігає суму [3]
позиція 4 зберігає суму [1–4]
позиція 5 зберігає суму [5]
позиція 6 зберігає суму [5–6]
позиція 7 зберігає суму [7]
позиція 8 зберігає суму [1–8]

Щоб знайти суму перших семи чисел, не потрібно читати всі сім:

[1–4] + [5–6] + [7]

У дереві це три комірки:

tree[4] + tree[6] + tree[7]

Вони не перетинаються й разом точно покривають позиції від першої до сьомої.

Якщо змінюється третє число, потрібно оновити лише блоки, до яких воно належить:

[3]
[1–4]
[1–8]

Тобто комірки:

tree[3]
tree[4]
tree[8]

Ось і вся основна ідея: дерево Фенвіка зберігає масив як набір блоків різного розміру. Великий потрібний відрізок складається з кількох готових блоків, а одна зміна торкається лише тих блоків, які містять змінений елемент.

Залишається зрозуміти, як програма знаходить ці блоки без окремої таблиці переходів.

Для цього й використовується дивний вираз i & -i.