Дерево Фенвика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал «Дерево фенвика» в «Дерево Фенвика»)
Строка 1: Строка 1:
= Дерево Фенвика (Binary indexed tree) =
 
 
{{Определение
 
{{Определение
 
| definition =
 
| definition =
'''Дерево Фе&#769;нвика''' - структура данных, требующая <tex> O(n) </tex> памяти и позволяющая эффективно (за <tex> O(log n) </tex>)
+
'''Дерево Фе&#769;нвика (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) - структура данных, требующая [math] O(n) [/math] памяти и позволяющая эффективно (за [math] O(log n) [/math])
  1. изменять значение любого элемента в массиве;
  2. выполнять некоторую бинарную операцию [math] G [/math] на отрезке [math] [i, j] [/math].

Впервые описано Питером Фенвиком в 1994 году.

Дерево Фенвика, запрос изменения элемента

Запрос получения суммы на префиксе

Полезные ссылки:

Peter M. Fenwick: A new data structure for cumulative frequency
Wikipedia: Fenwick tree
e-maxx.ru: Дерево Фенвика