Дерево Фенвика

Дерево Фенвика (Binary indexed tree)

Определение:

Дерево Фе́нвика - структура данных, требующая [math] O(n) [/math] памяти и позволяющая эффективно (за [math] O(log n) [/math]) изменять значение любого элемента в массиве; выполнять некоторую бинарную операцию [math] G [/math] на отрезке [math] [i, j] [/math].

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

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

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

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

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