146
правок
Изменения
Нет описания правки
[[Файл:Bit.jpg|thumb|300px|По горизонтали - содержимое массива <tex>T</tex> <br/> (<tex>T_i</tex> является суммой заштрихованных ячеек массива <tex>A</tex>),<br/> по вертикали - содержимое массива <tex>A</tex>]]
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i= [a_0, a_1, i = 0 .. . , a_{n - 1 }]</tex>.<br/>Деревом Фенвика будем называть массив <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> числа и его значения, увеличенного на единицу, мы получаем это число без последних подряд идущих единиц.
== Запрос изменения элемента ==
{{Лемма
|statement= Все такие <tex> i </tex> удовлетворяют равенству <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>, где <tex> \mid </tex> — это операция побитового логического "ИЛИ"<tex> OR </tex>.
|proof=Первый элемент последовательности само <tex> k </tex>. Для него выполняется равенство, так как <tex> F(i) \leqslant i </tex>. По формуле <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> мы заменим первый ноль на единицу. Неравенство при этом сохранится, так как <tex>F(i)</tex> осталось прежним или уменьшилось, а <tex> i </tex> увеличилось. Можем заметить, что если количество единиц в конце не будет совпадать с <tex> k </tex>, то формула <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex> нарушит неравенство, потому что либо само <tex> i </tex> будет меньше, чем k, либо <tex> F(i) </tex> станет больше, чем <tex> k </tex>. Таким образом, перебраны будут только нужные элементы}}
Все <tex>i</tex> мы можем получить следующим образом : <tex>i_{next} = i_{prev} \mid (i_{prev} + 1) </tex>. Следующим элементом в последовательности будет элемент, у которого первый с конца ноль превратится в единицу. Можно заметить, что если к исходному элементу прибавить единицу, то необходимый ноль обратится в единицу, но при этом все следующие единицы обнулятся. Чтобы обратно их превратить в единицы, применим операцию побитового ИЛИ<tex>OR</tex>. Таким образом все нули в конце превратятся в единицы и мы получим нужный элемент. Для того, чтобы понять, что эта последовательность верна, достаточно посмотреть на таблицу.
{| style="background-color:#CCC;margin:0.5px"
* [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf Peter M. Fenwick: A new data structure for cumulative frequency]
* [http://en.wikipedia.org/wiki/Fenwick_tree Wikipedia — Fenwick_tree Fenwick tree]
* [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Maximal:: algo:: Дерево Фенвика]
