⚡️ Fenwick Tree держится на одном битовом трюке

Fenwick Tree, или Binary Indexed Tree, считает prefix sums за O(log n).

Вся магия в операции:

i & -i

Она находит младший установленный бит числа.

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

В two’s complement число -i получается как инверсия битов i плюс 1.
Когда мы делаем i & -i, остаётся только самый правый бит, равный 1.

Например:

i = 12        // 1100
-i            // 0100 в нужной маске
i & -i = 4

Именно это значение говорит Fenwick Tree, на сколько нужно прыгнуть по индексам.

Для обновления:

for (; i < MAXN; i += i & -i)
    tree[i] += v;

Мы идём вверх по структуре и обновляем все узлы, которые покрывают этот индекс.

Для запроса суммы:

for (; i > 0; i -= i & -i)
    s += tree[i];

Мы идём вниз и собираем нужные блоки суммы.

Одна и та же операция управляет двумя направлениями:

* i += i & -i — перейти к следующему ответственному узлу
* i -= i & -i — убрать последний блок из prefix sum

Поэтому Fenwick Tree такой компактный:
никаких явных рёбер, указателей и рекурсии. Только массив и битовая арифметика.

Красота структуры в том, что дерево как бы спрятано внутри двоичного представления индекса.