НЯ!
Эта статья полна любви и обожания.
Возможно, стоит добавить ещё больше?

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

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

Определение

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

$$ t_i = \sum_{k=F(i)}^i a_k $$

где $F$ это какая-то функцию, для которой выполнено $F(i) \leq 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

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

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

Реализация

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

In [ ]:
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 перепишется следующим образом:

In [ ]:
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)$.

In [ ]:
// возвращает индекс, на котором сумма уже больше
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$.

Например,

$$ \begin{align} \begin{aligned} +90 = 2+8+16+64 & = 0 \, 10110_2 \\ -90 = 00000_2 - 10110_2 & = 1 \, 01010_2 \\ \implies (+90) \text{ & } (-90) & = 0 \, 00010_2 \\ \end{aligned} \end{align} $$

Вернёмся к доказательству леммы. Когда мы вычитаем, мы идем справа налево. В ответе можно мысленно разделить на три блока:

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

Делаем &: в каком-то префиксе все биты будут противоположными, младший единичный бит останется, а на суффиксе все как было нулями, так и осталось. Выживет только этот самый младший единичный бит.

Теперь сразу понятно, почему sum будет работать за логарифм — каждый раз мы делаем x -= x & -x, то есть удаляем один бит.

Теперь сложная (для понимания) часть — как делать add. Какие $t_i$ содержат $k$-й элемент? Для них должно выполняться i >= k > i - (i & -i).

Будем перебирать префиксы TODO

Мы знаем, что $t_i$ вложены друг в друга. Минимальный подходящий $i$ равен $k$. Какой следующий? Нам нужно для каждого $i$ уметь находить его непосредственного родителя.

Можно представить дерево так: ячейка 2^k содержит все

TODO: сначала объявить дерево как дерево и описать его структуру словами, а потом уже показывать реализацию.

Название

Потому что $F$ использует битовые операции, по-английски структура называется «Binary Indexed Tree».

Почему дерево Фенвика — дерево? Тут нужно немного воображения. На самом деле BIT в общем случае — набор деревьев.

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

В частном случае, когда длина массива равна $2^k$, то дерево будет только одно.