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; ;
Abstract The segment tree is a fundamental data structure for range queries and point updates. While recursive implementations are intuitive, they suffer from high constant factors due to function call overhead and conditional branching. This paper describes the zkw segment tree , a non‑recursive alternative introduced by Zhang Kunwei (zkw). By storing data in a perfect binary tree indexed from the bottom layer, it eliminates recursion entirely. The resulting implementation is shorter, faster, and particularly well‑suited for competitive programming and low‑latency systems. 1. Introduction A standard segment tree is usually built as an array tree[] of size about 4*N . Recursive functions traverse the tree to answer range sum/min/max queries or apply point updates. Despite its asymptotic $O(\log N)$ performance, recursion overhead and repeated bounds checking slow down execution.
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线段树
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 (!(r & 1)) res += tree[r]; r >>= 1; return res; By storing data in a perfect binary tree
Prefix sum [0, r] :
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. Introduction A standard segment tree is usually built
On a sum tree, find smallest p such that sum[0..p] >= k .