Одномерное дерево Фенвика — различия между версиями
(Новая страница: «''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции: # '''upd''' (update) в одно…») |
|||
| Строка 12: | Строка 12: | ||
* использует ''O(n)'' дополнительной памяти | * использует ''O(n)'' дополнительной памяти | ||
| − | |||
* легко обобщается на случай многомерных массивов. | * легко обобщается на случай многомерных массивов. | ||
Версия 13:32, 4 апреля 2020
Задача: Есть массив a0 ... an-1, хотим поддерживать операции:
- upd (update) в одной точке
apos += val - сумма на отрезке
- al + ... + ar – ?
Дерево Фенвика
Дерево Фенвика (англ. Binary Indexed Tree, BIT) – это структура данных, дерево на массиве, обладающее следующими свойствами:
- позволяет вычислять сумму на отрезке [l; r] за время O(log n)
- позволяет изменять значение любого элемента за O(log n)
- использует O(n) дополнительной памяти
- легко обобщается на случай многомерных массивов.
