Zkw线段树 - _best_

int prefix(int r) r += N; int res = 0; while (r) if (!(r & 1)) res += tree[r]; r >>= 1; return res;

template<typename T> class ZkwSegTree int N; vector<T> tree; public: ZkwSegTree(int n, const vector<T>& init) N = 1; while (N < n) N <<= 1; tree.assign(2*N, 0); for (int i = 0; i < n; i++) tree[N+i] = init[i]; for (int i = N-1; i; i--) tree[i] = tree[2*i] + tree[2*i+1]; void update(int p, T val) p += N; tree[p] = val; while (p >>= 1) tree[p] = tree[2*p] + tree[2*p+1]; T query(int l, int r) // inclusive l += N, r += N; T res = 0; while (l <= r) if (l & 1) res += tree[l++]; if (!(r & 1)) res += tree[r--]; l >>= 1; r >>= 1; return res; ; zkw线段树

Prefix sum [0, r] :

Time: $O(\log N)$ with very low constant. The core innovation is the closed interval query [l, r] (inclusive) using two pointers. int prefix(int r) r += N; int res = 0; while (r) if (

On a sum tree, find smallest p such that sum[0..p] >= k . int lower_bound(int k) int pos = 1; while

int lower_bound(int k) int pos = 1; while (pos < N) if (tree[pos<<1] < k) 1; else pos = pos<<1; return pos - N;