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