Одномерное дерево Фенвика: различия между версиями
Перейти к навигации
Перейти к поиску
Нет описания правки |
Нет описания правки |
||
| Строка 14: | Строка 14: | ||
* легко обобщается на случай многомерных массивов. | * легко обобщается на случай многомерных массивов. | ||
=== Описание === | === Описание === | ||
Текущая версия от 10: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) дополнительной памяти
- легко обобщается на случай многомерных массивов.