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

Дерево Фенвика — структура для префиксных сумм с изменениями. Она не упрощённое дерево отрезков, а другой инструмент: короче, быстрее по константе, занимает ровно $n$ чисел — и умеет заметно меньше.

	дерево отрезков	дерево Фенвика
память	$4n$	ровно $n$
код	40–80 строк	6 строк
операции	любые ассоциативные	обратимые и префиксные
отложенные пометки	есть	нет
многомерность	тяжело	цикл на измерение

Устройство

Ячейка $i$ хранит сумму отрезка длины i & -i, кончающегося в позиции $i$. Здесь i & -i — младший единичный бит числа.

void add(int at, Long delta) {
    for (int i = at; i <= n; i += i & -i) tree[i] += delta;
}

Long prefix(int at) {
    Long total = 0;
    for (int i = at; i > 0; i -= i & -i) total += tree[i];
    return total;
}

Подъём i += i & -i идёт к ячейке, которая накрывает текущую; спуск i -= i & -i отрезает уже учтённый кусок и переходит к соседнему слева. Обе цепочки имеют длину $O(\log n)$.

Сумма на отрезке — разность префиксов: prefix(r) - prefix(l - 1).

Индексы начинаются с единицы. При $i = 0$ получается 0 & -0 == 0, и цикл прибавления зацикливается — это не соглашение, а требование структуры.

Построение за линию

$n$ прибавлений дают $O(n \log n)$. Быстрее — заполнить дерево значениями и «протолкнуть» каждое в накрывающую ячейку:

for (int i = 1; i <= n; i++) tree[i] += values[i];
for (int i = 1; i <= n; i++) { int up = i + (i & -i); if (up <= n) tree[up] += tree[i]; }

Приём 1: массив разностей

Если в дереве держать не значения, а разности соседей $d_i = a_i - a_{i-1}$, операции меняются местами:

что хотим	что делаем
прибавить $v$ на $[l, r]$	add(l, v); add(r + 1, -v);
узнать $a_i$	prefix(i)

Если нужны и прибавление на отрезке, и сумма на отрезке, хватает двух деревьев. Из

$$\sum_{i=1}^{p} a_i = (p + 1)\sum_{j=1}^{p} d_j - \sum_{j=1}^{p} j \cdot d_j$$

видно, что второе дерево хранит $j \cdot d_j$. Прибавление пишет в оба дерева по две ячейки со сдвигами $v(l-1)$ и $-vr$.

Приём 2: дерево по значениям

Индекс — не позиция, а само число (после сжатия координат). Тогда префиксная сумма отвечает на «сколько добавленных меньше $x$», и этим решаются:

• количество инверсий: идём слева направо, спрашиваем «сколько уже больших»;
• порядковые статистики в изменяющемся мультимножестве;
• «сколько точек левее и ниже» после сортировки по одной координате.

Приём 3: спуск по битам

$k$-е по счёту находится за один логарифм, без двоичного поиска по префиксам:

int kth(Long k) {
    int pos = 0;
    for (int step = highestPower; step > 0; step >>= 1)
        if (pos + step <= n && tree[pos + step] < k) { pos += step; k -= tree[pos]; }
    return pos + 1;
}

Ячейка pos + step накрывает отрезок длины step. Если её суммы не хватает — весь отрезок левее ответа, сдвигаемся; иначе ответ внутри, уменьшаем шаг.

Приём 4: лишние измерения

Двумерное дерево Фенвика — два вложенных цикла по битам и массив $n \times m$:

for (int i = x; i <= n; i += i & -i)
    for (int j = y; j <= m; j += j & -j)
        tree[i][j] += value;

Запрос по прямоугольнику — четыре префикса со знаками включений-исключений, по параллелепипеду — восемь. В $d$ измерениях: $d$ циклов и $2^d$ слагаемых.

Ограничение тут не время, а память: $n^3$ чисел при $n = 128$ — шестнадцать мегабайт.

Чего оно не умеет

задача	дерево Фенвика
сумма на отрезке	умеет: разность префиксов
минимум на префиксе	умеет, если значения только уменьшаются
минимум на произвольном отрезке	нет
присвоение на отрезке	нет
любые отложенные пометки	нет

Причина одна: отрезок получается вычитанием, а вычитать можно только обратимое. Минимум и максимум необратимы — для них нужно дерево отрезков.

Где ошибаются

Индексация с нуля. Зацикливание в add. Самая частая ошибка и самая быстрая в поиске, если про неё помнить.

Тип суммы. При $n = 2 \cdot 10^5$ и значениях до $10^9$ сумма доходит до $2 \cdot 10^{14}$: 32 бита молча переполняются.

Граница $r + 1$ в разностях. Заведите дерево на $n + 1$ ячейку, и проверка исчезнет сама.

Сравнение < против <= в спуске. От него зависит, какой из равных элементов найдётся; проявляется только на повторяющихся значениях.

Смежное: дерево отрезков, массив разностей, дерево по значениям, сжатие координат.