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

⚡️ 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 такой компактный: никаких явных рёбер, указателей и рекурсии. Только массив и битовая арифметика. Красота структуры в том, что дерево как бы спрятано внутри двоичного представления индекса.