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

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;
}