Fenwick Tree

mail@pastecode.io avatar
unknown
c_cpp
a year ago
284 B
1
Indexable
Never
vector<int> bit;

void update(int index, int n) {
    for(;index <= n; index += index & (-index)) {
        bit[index]++;
    }
}

int query(int index) {
    int sum = 0;
    for(;index > 0; index -= index & (-index)) {
        sum += bit[index];
    }
    return sum;
}