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

Дерево Фенвика или двоичное индексированное дерево (англ. binary indexed tree) — структура данных, которая на многих задачах заменяет собой дерево отрезков, но при этом работает в 3-4 раза быстрее, занимает минимально возможное количество памяти (столько же, сколько и массив той же длины), намного быстрее пишется и легче обобщается на большие размерности.

Определение

Пусть дан массив $a$ длины $n$. Деревом Фенвика будем называть массив $t$ той же длины, объявленный следующим образом:

$$t_i=\sum _{k=F(i)}^i{a}_k$$

где $F$ это какая-то функцию, для которой выполнено $F(i)\le i$. Конкретно её определим потом.

Запрос суммы. Когда нам нужна сумма на отрезке, мы будем сводить этот запрос к двум суммам на префиксе: $sum(l,r)=sum(r)-sum(l-1)$. Оба этих запроса будем считать по формуле:

$$sum(k)=t_k+sum(F(k)-1)$$

Запрос обновления. Когда мы изменяем $k$-ю ячейку исходного массива, мы обновляем все $t_i$, в которых учтена эта ячейка.

$F$ можно выбрать так, что и «спусков» при подсчете суммы, и интересных нам $t_i$ при обновлении будет будет $O(\log n)$. Популярны две функции:

• $F_1(x)=$ x & (x + 1)
• $F_2(x)=$ x - (x & -x) + 1

Первый вариант описан на Викиконспектах и Емаксе и поэтому более известен. Второй, как мы дальше увидим, более простой для запоминания и кодинга, а так же более гибкий — например, там можно делать бинпоиск по префиксным суммам. Его мы и будем использовать.

Примечание. Наверное, меньше четверти умеющих писать эту структуру полностью понимают, как она работает. Анализ действительно весьма сложный, поэтому мы приведём его в конце. Рекумендуется пока что абстрагироваться и принять на веру, что любой префикс разбивается на $O(\log n)$ отрезков вида $[F(i),i]$, а также что любой элемент входит в не более $O(\log n)$ таких отрезков.

Реализация

Так как $F(0)=1>0$, то $[0,F(0)]$ не является корректным отрезком. Поэтому нам будет удобнее хранить массив в 1-индексации и не использовать $t_0$.

int t[maxn];

// возвращает сумму на префиксе
int sum (int r) {
    int res = 0;
    for (; r > 0; r -= r & -r)
        res += t[r];
    return res;
}

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

// обновляет нужные t
void add (int k, int x) {
    for (; k <= n; k += k & -k)
        t[k] += x;
}

Автор отмечает красивую симметрию в формулах r -= r & -r и k += k & -k, которой нет в «традиционной» версии.

Многомерный случай

$k$-мерное дерево Фенвика пишется в $(k+1)$ строчку

Нужно добавить всего одну такую же строчку в sum, add, а также при подсчете суммы на прямоугольнике вместо двух запросов к префиксным суммам использовать четыре.

sum перепишется следующим образом:

int sum (int r1, int r2) {
    int res = 0;
    for (int i = r1; i > 0; i -= i & -i)
        for (int j = r2; j > 0; j -= j & -j)
            ans += t[i][j];
    return res;
}

В $k$-мерном случае, в соответствии с принципом включений-исключений, для запроса суммы нужно $2^k$ запросов суммы на префиксах.

Если размерности больше, чем позволяет память, то можно вместо массива t использовать хэш-таблицу — так потенциально потребуется $O(q{\log }^{2}A)$ памяти ($A$ — максимальная координата), но это всё равно один из самых безболезненных способов решать достаточно простые задачи на двумерные структуры. Автор в своё время таким образом решил какую-то задачу на 2d-сумму с USACO 2017.

Бинпоиск

Оказывается, можно производить бинарный поиск (точнее, спуск) по префиксным суммам за $O(\log n)$.

// возвращает индекс, на котором сумма уже больше
int lower_bound (int s) {
    int k = 0;
    for (int l = logn; l >= 0; l--) {
        if (k + (1<<l) <= n && t[k + (1<<l)] < s) {
            k += (1<<l);
            s -= t[k];
        }
    }
    return k;
}

Если знать, что $F(x)$ удаляет последний бит $x$, то принцип понятен: просто делаем спуск по бинарному дереву, как в ДО. Чем-то похоже на генерацию $k$-го лексикографического комбинаторного объекта: пытаемся увеличить следующий символ всегда, когда это возможно.

Отметим, что в «традиционной» индексации такое делать нельзя.

Ограничения на операцию

Дерево Фенвика можно использовать, когда наша операция обратима, а также когда трюк с префиксными суммами работает. Это обычно простые операции типа суммы, xor, умножения по модулю (если гарантируется, что на этот модуль ничего не делится). Минимум и gcd, отложенные операции и персистентность прикрутить в общем случае уже не получится — тогда уже нужно писать дерево отрезков.

Почему это работает

Итак, мы выбрали вариант с $F(x)$ = x - (x & -x) + 1. Поймем, что означает x & -x.

Лемма. x & -x возвращает последний единичный бит в двоичной записи x.

Доказательство потребует знания, как в компьютерах хранятся целые числа. Чтобы процессор не сжигал лишние такты, проверяя знак числа при арифметических операциях, их хранят как бы по модулю $2^k$, а первый бит отвечает за знак (0 для положительных и 1 для отрицательных). Поэтому когда мы хотим узнать, как выглядит отрицательное число, нужно его вычесть из нуля: $-x=0-x=2^k-x$.

Как будет выглядеть -x в битовой записи? Ответ можно мысленно разделить на три блока:

• Первые сколько-то (возможно, нисколько) нулей с конца числа x ими же в ответе и останутся.
• Потом, ровно на самом младшем единичном бите x, мы «займём» много единиц, так что весь префикс станет единицами. В ответе на этом месте точно будет единица.
• Потом отменятся ровно те биты из этого префикса, которые были единицами в исходном числе.

Пример:

$$\begin{array}{rl}+90=2+8+16+64& =0{10110}_2\\ -90={00000}_2-{10110}_2& =1{01010}_2\\ ⟹(+90)\mathrm{\&}(-90)& =0{00010}_2\end{array}$$

Теперь мы можем доказать нашу лемму. Когда мы сделаем &, в префиксе до младшего единичного бита все биты x и -x будут противоположными, младший единичный бит останется единичным, а на суффиксе все как было нулями, так и осталось. Следовательно, «выживет» только этот самый младший единичный бит, что мы и доказывали.

Следствие 1. sum будет работать за логарифм, а точнее за количество единичных битов в записи $x$: на каждой итерации мы делаем x -= x & -x, то есть удаляем младший бит.

Следствие 2. add тоже будет работать за логарифм: каждую итерацию количество нулей на конце $x$ увеличивается хотя бы на единицу.

Следствие 3. (Почему дерево Фенвика — дерево.)

• Длина отрезка, соответствующего любому $t_i$ — степень двойки, причём начинается этот отрезок на индексе, кратном этой же степени двойки.

• $⟹$ Множества элементов, учтённых в произвольных $t_i$ и $t_j$, либо не пересекаются, либо одно является подмножеством другого.

• $⟹$ На $t_i$ можно ввести отношение вложенности.

То есть, если напрячь воображение, то $t$ можно рассматривать как лес деревьев. В частном случае, когда $n$ является степенью двойки, дерево будет одно.

Теперь единственное, что осталось доказать ­— это корректность add. На самом деле, в add мы делаем ни что иное, как подъём от вершины до корня по всем предкам.

Как для $x$ найти непосредственного родителя? Нужно найти минимальное число $y>x$, у которого $t_y$ будет включать $x$. Иными словами, должно выполняться y >= x > y - (y & -y).

Дальше читателю предлагается самостоятельно попялиться в пример, чтобы понять, что x + (x & -x) — минимальное такое число:

$$\begin{array}{rl}x=90=2+8+16+64& ={10110}_2\\ y=96=32+64& ={11000}_2\end{array}$$