Дерево Фенвика — это структура данных, которая поддерживает следующие функции:
Основная идея чем-то похожа на дерево отрезков. Создаются ровно отрезков, в которых мы будем хранить сумму элементов этого отрезка. Так, чтобы:
Далее создается массив .
В будем хранить сумму элементов .
И возникает вопрос: какие именно отрезки нужно строить? То есть какие значения брать?
— это число, полученное инвертированием последнего бита в двоичном представлении .
Например:
Можно заметить, что:
Это все позиции , для которых выполняется:
А все такие позиции можно получить так:
Почему это работает — можно оставить как упражнение для читателя.
while (i <= n) {
...
i += (i & -i);
}
struct fenwick {
vector<long long> t;
fenwick(int n) : t(n, 0) {}
void upd(int x, long long y) {
while (x < (int)t.size()) {
t[x] += y;
x += x & -x;
}
}
long long get(int x) {
long long res = 0;
while (x > 0) {
res += t[x];
x -= x & -x;
}
return res;
}
};