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

Дерево Фенвика или двоичное индексированное дерево (англ. 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

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

Примечание. Наверное, меньше четверти умеющих писать эту структуру полностью понимают, как она работает. Анализ действительно весьма сложный, поэтому мы приведём его в конце. Рекумендуется пока что абстрагироваться и принять на веру, что любой префикс разбивается на \(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{aligned} +90 = 2+8+16+64 & = 0 \, 10110_2 \\ -90 = 00000_2 - 10110_2 & = 1 \, 01010_2 \\ \implies (+90) \& (-90) & = 0 \, 00010_2 \\ \end{aligned} \]

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

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

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

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

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

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

• \(\implies\) На \(t_i\) можно ввести отношение вложенности.

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

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

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

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

\[ \begin{aligned} x = 90 = 2+8+16+64 & = 10110_2 \\ y = 96 = 32 + 64 & = 11000_2 \\ \end{aligned} \]