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

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_Фенвика&oldid=8281»