Как устроено дерево Фенвика и почему трюк i & (-i) даёт следующий/предыдущий индекс?
Хочу понять Фенвик (BIT) до конца, а не заучить две строчки. Что именно хранится в t[i], почему обновление идёт i += i & -i, а запрос — i -= i & -i, и при чём тут младший установленный бит? Нужна реализация на C++ с асимптотикой.
2 ответа
t[i] хранит сумму отрезка длины lowbit(i) = i & -i — это блок [i - lowbit(i) + 1, i]. Младший установленный бит задаёт длину «зоны ответственности» узла, поэтому дерево неявно бьёт массив на блоки степеней двойки.
- Префиксная сумма
[1..i]: спускаемся, отрезая младший бит — складываем непересекающиеся блоки, покрывающие префикс. - Точечное обновление
a[i] += v: поднимаемся по всем узлам, чьи блоки накрывают i — добавляем младший бит.
struct BIT {
int n; vector<long long> t;
BIT(int n): n(n), t(n+1, 0) {}
void update(int i, long long v){ // a[i] += v, индексация с 1
for (; i <= n; i += i & -i) t[i] += v;
}
long long query(int i){ // сумма a[1..i]
long long s = 0;
for (; i > 0; i -= i & -i) s += t[i];
return s;
}
};
Почему i & -i = младший бит: в дополнительном коде -i = ~i + 1, и при сложении все младшие нули и первая единица «выживают», старшие биты обнуляются — остаётся ровно младшая единица. Двигаясь по битам, мы за каждый шаг гасим/добавляем один блок, поэтому и update, и query делают не больше log₂n шагов: O(log n) время, O(n) память. Это и есть вся магия — индексация по битам.
Совет по интуиции: нарисуйте узлы для n=8 и подпишите длины блоков (t[1]→1, t[2]→2, t[4]→4, t[8]→8, t[6]→2 и т.д.). Сразу видно, что query(6)=t[6]+t[4] (блоки [5,6] и [1,4]), а update(5) трогает t[5],t[6],t[8]. После такой картинки i&-i перестаёт быть «заклинанием». И сразу привыкайте к long long в сумме — int переполнится почти на любой олимпиадной задаче с n·max до 10^14.