272
правки
Изменения
Нет описания правки
{{Определение
| definition =
'''Дерево Фенвика Фе́нвика''' - структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(log n) </tex>)# изменять значения значение любого элемента в массиве и ;# выполнять некоторую бинарную операцию <tex> G </tex> на отрезке<tex> [i, j] </tex>.
}}
Впервые описано Питером Фенвиком в 1994 году.
== Дерево Фенвика, запрос изменения элемента ==
== Запрос получения суммы на префиксе ==
== Полезные ссылки: ==
Peter M. Fenwick: [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=F180153B9C0CD797594314B736E2CCC5?doi=10.1.1.14.8917&rep=rep1&type=pdf A new data structure for cumulative frequency]<br/>Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree]<br/>
e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика]
