Simple Fenwick (binary indexed tree) tree implementation

bit.cpp

#define MAXSZ 200001
int sum[MAXSZ];

inline void init(int sz){
    fill_n(sum, sz + 1, 0);
}

inline void update(int* arr, int sz, int idx, int val)
{
    while(idx <= sz){
        arr[idx] += val;
        idx += (idx & -idx);
    }
}
inline int prefixsum(int* arr, int idx){
    auto sum = 0;
    while (idx> 0){
        sum += arr[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

inline int query(int* arr, int l, int r){
    return prefixsum(arr, r) - ((l > 1) ? prefixsum(arr, l - 1) : 0);
}