Zkw线段树 ((free)) May 2026

l and r climb up. When l is a right child, its parent covers an interval that starts before l , so we take tree[l] and move l right. Symmetrically for r . 5. Comparison with Recursive Segment Tree | Aspect | Recursive Segment Tree | zkw Segment Tree | |----------------------|---------------------------------|----------------------------------| | Code length | ~40 lines (build, update, query)| ~15 lines total | | Memory | usually 4*N | exactly 2*N | | Recursion | yes (overhead + risk of stack) | none (loops only) | | Speed (log N range) | baseline (1×) | ~2–3× faster | | Lazy propagation | straightforward | more complex (but possible) | | Ease of debugging | moderate | easy (no recursion stack) | 6. Advanced Operations 6.1 Prefix / Suffix Queries For [0, r] or [l, N-1] , the code simplifies.

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

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; ; l and r climb up

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

Prefix sum [0, r] :

On a sum tree, find smallest p such that sum[0..p] >= k .