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

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

Дерево Фе́нвика (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: Дерево Фенвика