Дерево Фенвика — различия между версиями
(Новая страница: «= Дерево Фенвика (Binary indexed tree) = {{Определение | definition = Дерево Фенвика - структура данных, позв…») |
|||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
| definition = | | definition = | ||
| − | Дерево | + | '''Дерево Фе́нвика''' - структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(log n) </tex>) |
| + | # изменять значение любого элемента в массиве; | ||
| + | # выполнять некоторую бинарную операцию <tex> G </tex> на отрезке <tex> [i, j] </tex>. | ||
}} | }} | ||
Впервые описано Питером Фенвиком в 1994 году. | Впервые описано Питером Фенвиком в 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] | + | 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/> | |
| − | Wikipedia: [http://en.wikipedia.org/wiki/Fenwick_tree Fenwick tree] | ||
| − | |||
e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] | e-maxx.ru: [http://e-maxx.ru/algo/fenwick_tree Дерево Фенвика] | ||
Версия 05:51, 1 мая 2011
Содержание
Дерево Фенвика (Binary indexed tree)
| Определение: |
Дерево Фе́нвика - структура данных, требующая памяти и позволяющая эффективно (за )
|
Впервые описано Питером Фенвиком в 1994 году.
Дерево Фенвика, запрос изменения элемента
Запрос получения суммы на префиксе
Полезные ссылки:
Peter M. Fenwick: A new data structure for cumulative frequency
Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика
