Дерево Фенвика (Fenwick tree)

Изумительная структура данных. Классический пример гениальной мысли.

Дерево Фенвика позволяет за O(log(N)) определять значение обратимой функции на интервале массива [L,R].

Обратимая функция:
1) Сумма на интервале    [L,R]
2) Минимум на интервале 
3) Максимум на интервале

Теория:
1) Статья Алексея Лахно
2) Статья Максима Иванова.

Осознать сам подход поможет это изображение:

Запомним два правила.
1) При добавлении нового элемента делаем подъем вверх

2) При подсчете суммы элементов в интервале [0,X] делаем спуск вниз

Реализация:

1. vector<int> b(MAX_VALUE+1);
2.  
3. void add(int x, int delta) {
4.   for (; x <= MAX_VALUE; x = x | (x + 1))
5.     b[x] += delta;
6. }
7.  
8. int sum(int x) {
9.   int res = 0;
10.   for (; x >= 0; x = (x & (x + 1)) - 1)
11.     res += b[x];
12.   return res;
13. }

* This source code was highlighted with Source Code Highlighter.

Практика:
Задача: 1028 (acm.timus.ru)
Решение: здесь

P.S: Не забываем, что дерево Фенвика легко интерпретируется на многомерный случай