树状数组写法

树状数组写法

标准写法

template <int N>
struct fenwick {int t[N + 1];void add(int x, int k) {for (; x <= N; x += x & -x) t[x] += k;}int query(int x, int r = 0) {for (; x >= 1; x -= x & -x) r += t[x];return r;}
};

查询后缀和

template <int N>
struct fenwick {int t[N + 1];void add(int x, int k) {for (; x >= 1; x -= x & -x) t[x] += k;}int query(int x, int r = 0) {for (; x <= N; x += x & -x) r += t[x];return r;}
};

0-indexed

template <int N>
struct fenwick {int t[N];void add(int x, int k) {for (; x < N; x |= x + 1) t[x] += k;}int query(int x, int r = 0) { // [0, x)for (; x--; x &= x + 1) r += t[x];return r;}
};