fenwick_tree.cpp

//fenwick_tree.cpp
//complexity:
//  update - O(log n)
//  query - O(log n)
//  sum_range - O(log n)
// binary_fenwick - O(log n)

const int maxN = 100002;
int ft[maxN];

void update(int x, int v){
    while(x < maxN){   
        ft[x] += v;
        x += x&-x;
    }
}

int query(int x){
    int ans = 0;
    while(x > 0){
        ans += ft[x];
        x -= x&-x;
    }
    return ans;
}

int sum_range(int l, int r){
    return query(r) - query(l-1);   
}

int read_individual(int x){ // x = prefix 1 0 ... 0  /  x-1 = prefix 0 1 ... 1 
    if(x == 0) return 0;
    int ans = ft[x];
    int parent = x&(x-1); // x -= x&-x; / parent = prefix 0 0 ... 0
    x -= 1;
    
    while(parent != x){
        ans -= ft[x];
        x = x&(x-1);
    }
    return ans;
}