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

Определение
Дерево Фенвика (англ. Binary indexed tree) — структура данных, требующая O(n) памяти и позволяющая эффективно (за O(log(n))) выполнять следующие операции:
изменять значение любого элемента в массиве,
выполнять некоторую ассоциативную, коммутативную, обратимую операцию на отрезке [i,j] (обычно это сумма).
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Основная идея
Представим бинарное дерево, в листьях которого хранятся значения исходного массива, а в остальных вершинах – сумма значений в детях этих вершин.
Вместо того, что бы хранить все вершины дерева, будем хранить значения только выделенных вершин. Заметим, что просуммировав значения в определённом наборе закрашенных вершин, можно получить сумму на любом префиксе исходного массива.
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Принцип работы
Для массива A будем хранить массив Т такой, что T[i] равно сумме элементов массива А на отрезке [i – 2k + 1; i], где k – это максимальное число, для которого i + 1 делится на 2k без остатка.
При изменении значения А[i] в массиве Т следует изменить все элементы, значение которых учитывает A[i]. Первый элемент будет иметь такой же индекс i, а для последующих вычисляется по формуле iновое = iстарое | (iстарое + 1), пока iновое не станет больше размера массива.
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Принцип работы
Для вычисления суммы на отрезке [0; r] массива А нужно сложить элементы массива Т, начиная с индекса r, где каждый следующий индекс вычисляется по формуле iновое = iстарое & (iстарое + 1) – 1, пока iновое не станет меньше 0.
Для вычисления суммы на отрезке [l; r] массива А достаточно вычесть из суммы на отрезке [0; r] сумму на отрезке [0; l – 1], каждую из которых можно вычислить по алгоритму, описанному выше.
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Реализация

Реализация (продолжение)

Реализация двухмерного случая

Задача
Дан массив целых чисел размером N и Q запросов. Запрос типа 1 прибавляет некоторое X ко всем элементам на отрезке [l; r]
(0 ≤ l ≤ r < N). Запрос типа 0 просит узнать значение элемента с индексом id (0 ≤ id < N) после всех предыдущих запросов.
Решение:
Заведём массив B размера N + 1 для хранения изменений, изначально заполненный нулями.
При получении запроса прибавления, будем прибавлять X к элементу массива В с индексом l и отнимать Х от элемента того же массива с индексом r + 1.
При получении запроса на значение элемента с индексом id будем прибавлять к начальному значению этого элемента сумму первых id элементов из массива B.

Реализация за O(N2)

Задача
Необходимо посчитать количество инверсий в массиве A. Количество инверсий – это количество таких пар чисел i и j, что i < j и A[i] > A[j].
Решение:
Заведём массив B размера Amax + 1, где Amax равно максимально возможному значению элемента массива А, и заполним его нулями. Переберём все элементы массива А. Для каждого элемента A[i] будем проставлять значение B[A[i]] равное 1. Тогда при рассмотрении A[i] количество элементов A[j] таких, что i > j и A[i] < A[j], будет равно сумме элементов массива В на отрезке [A[i] + 1; Amax], что является количеством инверсий, в которых меньший элемент – A[i]. Сумма этих сумм и будет являться количеством инверсий всего массива А.