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

Материал из Викиконспекты
Версия от 05:37, 1 мая 2011; Андрей Козлов (обсуждение | вклад) (Новая страница: «= Дерево Фенвика (Binary indexed tree) = {{Определение | definition = Дерево Фенвика - структура данных, позв…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Определение:
Дерево Фенвика - структура данных, позволяющая эффективно изменять значения в массиве и выполнять некоторую бинарную операцию G на отрезке.

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

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

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

Peter M. Fenwick: A new data structure for cumulative frequency

Wikipedia: Fenwick tree

e-maxx.ru: Дерево Фенвика