146
правок
Изменения
Нет описания правки
'''Дерево Фе́нвика''' (англ. ''Binary indexed tree'') — структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(\log n) </tex>):
* изменять значение любого элемента в массиве,
* выполнять некоторую ассоциативную, коммутативную, обратимую операцию <tex> G \circ </tex> на отрезке <tex> [i, j] </tex>.
[[Файл:Bit.jpg|thumb|300px|По горизонтали - содержимое индексы массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой заштрихованных ячеек элементов массива <tex>A</tex>, индексы которых заштрихованы),<br/> по вертикали - содержимое индексы массива <tex>A</tex>]]
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив <tex> A = [a_0, a_1, ... , a_{n - 1}]</tex>.
Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k</tex>, где <tex> 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>AND</tex>. При <tex>AND</tex> числа и его значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.
== Запрос изменения элемента ==
Нам надо научиться быстро изменять частичные суммы в зависимости от того, как изменяются элементы. Рассмотрим как изменять величину изменяется массив <tex>a_{k}T</tex> при изменении элемента <tex>a_k</tex>.
{{Лемма
|statement=
