Дерево Фенвика
Дерево Фенвика — это структура данных, дерево на массиве. Свойства:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время; • позволяет изменять значение любого элемента за O(log N); • требует памяти O(N);
Описание.
Для простоты описания мы предполагаем, что операция G, по которой мы строим дерево, - это сумма. Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:
Ti = сумма Aj для всех F(i) <= j <= i,
где F(i) - некоторая функция, которую мы определим несколько позже. Теперь мы уже можем написать код для функции вычисления суммы на отрезке [0; R] и для функции изменения ячейки.
Функция sum в место того чтобы идти по всем элементам массива A, движется по массиву T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F(R); R], затем берёт сумму на отрезке [F(F(R)-1); F(R)-1], и так далее, пока не дойдёт до нуля.
Функция upd движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j. Очевидно, что от выбора функции F будет зависеть скорость выполнения обеих операций.
Определим значение F(X) следующим образом: F(X) = X & (X+1),
Нахождение F(j) <= i <= j соответствует формуле: H(X) = X | (X+1)