A Fenwick tree is a data structure that supports the following functions:
The main idea is somewhat similar to a segment tree. Exactly segments are created, in which we will store the sum of the elements of that segment. So that:
Next, an array is created.
In we will store the sum of elements .
And the question arises: which segments exactly need to be built? That is, which values of should be taken?
is the number obtained by inverting the last bit in the binary representation of .
For example:
You can notice that:
These are all positions for which the following holds:
And all such positions can be obtained like this:
Why this works can be left as an exercise for the reader.
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;
}
};