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

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

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

a_l + ... + a_r – ?

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

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

• позволяет вычислять сумму на отрезке [l; r] за время O(log n)

• позволяет изменять значение любого элемента за O(log n)
  

• использует O(n) дополнительной памяти

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