146
правок
Изменения
Нет описания правки
Впервые описано Питером Фенвиком в 1994 году.
Пусть дан массив <tex> A </tex> из <tex> n </tex> элементов: <tex> a_i, i = \overline{0, .. n - 1} </tex>.<br/>Деревом Фенвика будем называть массив <tex> T </tex> из <tex> n </tex> элементов: <tex> T_i = \sum\limits_{k = F(i)}^{i} a_k, i = \overline{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 \& And (i + 1) </tex>.
== Запрос изменения элемента ==
Необходимо изменить элементы дерева <tex>T_{i}</tex>, для которых верно неравенство <tex>F(i) \leq k \leq i</tex> .
|proof=
<tex> T_i =\sum\limits_{k = F(i)}^{i} a_k , i = \overline{0, .. n - 1} \Rightarrow</tex> необходимо менять те <tex>i</tex>, для которых <tex>a_{k}</tex> попадает в <tex>T_i \Rightarrow</tex> необходимые <tex> i </tex> удовлетворяют условию <tex>F(i) \leq k \leq i</tex>.
}}
Напишем функцию, которая будет изменять элемент <tex>a_i</tex> на <tex>d</tex>, и при этом меняет соответствующие частичные суммы.
== Запрос получения суммы на префиксе ==
</code>
== Полезные ссылки: Источники информации==Peter M. Fenwick: * [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] <br/>Wikipedia: * [http://en.wikipedia.org/wiki/Wikipedia — Fenwick_tree Fenwick tree] <br/>e-maxx.ru: * [http://e-maxx.ru/algo/fenwick_tree e-maxx.ru — Дерево Фенвика]
