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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал «Дерево фенвика» в «Дерево Фенвика»)
(нет различий)

Версия 05:55, 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: Дерево Фенвика