Одномерное дерево Фенвика

Материал из Public ATP Wiki
Перейти к: навигация, поиск

Задача: Есть массив a0 ... an-1, хотим поддерживать операции:

  1. upd (update) в одной точке
    apos += val
  2. сумма на отрезке
al + ... + ar – ?

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

Дерево Фенвика (англ. Binary Indexed Tree, BIT) – это структура данных, дерево на массиве, обладающее следующими свойствами:

  • позволяет вычислять сумму на отрезке [l; r] за время O(log n)
  • позволяет изменять значение любого элемента за O(log n)
  • использует O(n) дополнительной памяти
  • легко обобщается на случай многомерных массивов.


Описание