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

Материал из Public ATP Wiki
Версия от 13:31, 4 апреля 2020; Algocourselecturenotes (обсуждение | вклад) (Новая страница: «''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции: # '''upd''' (update) в одно…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача: Есть массив 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) дополнительной памяти


  • легко обобщается на случай многомерных массивов.


Описание

Источник — «http://wiki.atp-fivt.org/index.php?title=Одномерное_дерево_Фенвика&oldid=272»