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

Дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

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

3) требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

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

Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика было впервые описано в статье "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

Описание

Для простоты описания мы предполагаем, что операция G, по которой мы строим дерево, - это сумма.

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:

Ti = сумма Aj для всех F(i) <= j <= i,

где F(i) - некоторая функция, которую мы определим несколько позже.

Теперь мы уже можем написать псевдокод для функции вычисления суммы на отрезке [0; R] и для функции изменения ячейки:

int sum (int r)
{
 int result = 0;
 while (r >= 0) {
 result += t[r];
 r = f(r) - 1;
 }
 return result;
}

void inc (int i, int delta)
{
 для всех j, для которых F(j) <= i <= j
 {
 t[j] += delta;
 }
}

Функция sum работает следующим образом. Вместо того чтобы идти по всем элементам массива A, она движется по массиву T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F(R); R], затем берёт сумму на отрезке [F(F(R)-1); F(R)-1], и так далее, пока не дойдёт до нуля.

Функция inc движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы T_j только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j.

Очевидно, что от выбора функции F будет зависеть скорость выполнения обеих операций. Сейчас мы рассмотрим функцию, которая позволит достичь логарифмической производительности в обоих случаях.

Определим значение F(X) следующим образом. Рассмотрим двоичную запись этого числа и посмотрим на его младший бит. Если он равен нулю, то F(X) = X. Иначе двоичное представление числа X оканчивается на группу из одной или нескольких единиц. Заменим все единицы из этой группы на нули, и присвоим полученное число значению функции F(X).

Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1),

где & - это операция побитового логического "И".

Нетрудно убедиться, что эта формула соответствует словесному описанию функции, данному выше.

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j.

Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого правого (самого младшего) нуля в двоичном представлении. Например, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д.

Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:

H(X) = X | (X+1),

где | - это операция побитового логического "ИЛИ".

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

vector<int> t;
int n;

void init (int nn)
{
 n = nn;
 t.assign (n, 0);
}

int sum (int r)
{
 int result = 0;
 for (; r >= 0; r = (r & (r+1)) - 1)
 result += t[r];
 return result;
}

void inc (int i, int delta)
{
 for (; i < n; i = (i | (i+1)))
 t[i] += delta;
}

int sum (int l, int r)
{
 return sum (r) - sum (l-1);
}

void init (vector<int> a)
{
 init ((int) a.size());
 for (unsigned i = 0; i < a.size(); i++)
 inc (i, a[i]);
}

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

Следует сразу заметить, что, поскольку дерево Фенвика позволяет найти значение функции в произвольном отрезке [0;R], то мы никак не сможем найти минимум на отрезке [L;R], где L > 0. Далее, все изменения значений должны происходить только в сторону уменьшения (опять же, поскольку никак не получится обратить функцию min). Это значительные ограничения.

vector<int> t;
int n;

const int INF = 1000*1000*1000;

void init (int nn)
{
 n = nn;
 t.assign (n, INF);
}

int getmin (int r)
{
 int result = INF;
 for (; r >= 0; r = (r & (r+1)) - 1)
 result = min (result, t[r]);
 return result;
}

void update (int i, int new_val)
{
 for (; i < n; i = (i | (i+1)))
 t[i] = min (t[i], new_val);
}

void init (vector<int> a)
{
 init ((int) a.size());
 for (unsigned i = 0; i < a.size(); i++)
 update (i, a[i]);
}

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

Как уже отмечалось, дерево Фенвика легко обобщается на многомерный случай.

vector <vector <int> > t;
int n, m;

int sum (int x, int y)
{
 int result = 0;
 for (int i = x; i >= 0; i = (i & (i+1)) - 1)
 for (int j = y; j >= 0; j = (j & (j+1)) - 1)
 result += t[i][j];
 return result;
}

void inc (int x, int y, int delta)
{
 for (int i = x; i < n; i = (i | (i+1)))
 for (int j = y; j < m; j = (j | (j+1)))
 t[i][j] += delta;
}