146
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Дерево Фе́нвика ''' (англ. ''Binary indexed tree)''' ) — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>)
# изменять значение любого элемента в массиве;
# выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G </tex> на отрезке <tex> [i, j] </tex>.
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = 0 .. n - 1 </tex>.<br/>
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k, i = 0 .. n - 1 </tex>, где <tex> F(i) </tex> - — некоторая функция.
От выбора функции зависит время работы операций над деревом. Рассмотрим функцию, позволяющую делать обе операции за время <tex> O(\log n) </tex>.
<tex> F(i) = i - 2^{h(i)} + 1, </tex> где <tex> h(i) </tex> - количество единиц в конце бинарной записи числа <tex> i </tex>. Эту функцию можно записать так: <tex> F(i) = i - t(i), </tex> где <tex> t(i) = 2^{h(i)} - 1, </tex> то есть число, состоящее из <tex> i </tex> единиц. Это значит, что функция заменяет все подряд идущие единицы в конце числа на нули.
Эта функция задается простой формулой: <tex> F(i) = i \And (i + 1) </tex>, где <tex> \And </tex> — это операция побитового логического "И". При побитовом "И" числа и этого числаего значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.
== Запрос изменения элемента ==
Напишем функцию, которая будет изменять элемент <tex>a_i</tex> на <tex>d</tex>, и при этом меняет соответствующие частичные суммы.
'''function''' modify(i, d): '''while ''' i < N
t[i] += d
i = i | (i + 1)
=== Реализация ===
Приведем код функции <tex> \mathrm sum(i) </tex> на C++: <code> '''int ''' sum(int i) {: int result = 0; '''while (''' i >= 0) {
result += t[i];
i = f(i) - 1;
==Преимущества и недостатки дерева Фенвика==
