Fenwick Tree
A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
Implementation
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> fenwickTree;
void update(int idx, int v) {
while(idx < fenwickTree.size()) {
fenwickTree[idx] += v;
idx = idx + (idx & -idx);
}
}
int query(int idx) {
int res = 0;
while(idx > 0) {
res += fenwickTree[idx];
idx = idx - (idx & -idx);
}
return res;
}
|
