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

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

  1. позволяет вычислять значение некоторой обратимой операции \(G\) на любом отрезке \([L; R]\) за время \(O(log(n)\);
  2. позволяет изменять значение любого элемента за \(O(log(n)\);
  3. требует \(O(n)\) памяти, а точнее, ровно столько же, сколько и массив из \(O(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\):

\(T_i\) = сумма \(A_j\) для всех \(F(i) <= j <= i\), где \(F(i)\) - некоторая функция, которую мы определим несколько позже.

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

int f(int x) {
   return x & (x + 1);
}

int h(int x) {
    return x | (x + 1);
}

ll sum(int index) {
   ll result = 0;
   while (index >= 0) {
      result += fenwick[index];
      index = f(index) - 1;
   }
   return result;
}

void edit(int index, ll element) {
   int a_index = index;
   while (index < fenwick.size()) {
      fenwick[index] += (element - a[a_index]);
      index = h(index);
   }
}

Функция \(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)\).

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

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

где \(\&\) - это операция побитового логического «И».

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

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

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

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

\[H(X) = X | (X+1)\]

где \(|\) - это операция побитового логического «ИЛИ».