🗂️Data StructureIntermediate

Iterative Segment Tree

Key Points

  • •
    An iterative segment tree stores all leaves in tree[n..2n-1] and internal nodes in tree[1..n-1], enabling O( n) point updates and range queries without recursion.
  • •
    Range queries are answered by moving two pointers l and r upward toward the root while merging partial answers, typically on the half-open interval [l, r).
  • •
    Point updates are done by changing a leaf and repeatedly recomputing its ancestors ("pulling up").
  • •
    Because it avoids function calls, the iterative version is faster in practice than a recursive segment tree for the same operations.
  • •
    The operation used to merge nodes must be associative, and an identity element must exist for clean querying.
  • •
    Building an iterative segment tree from an array takes O(n) time and O(n) extra memory (2n total cells).
  • •
    Iterative lazy propagation is possible but trickier; a common approach rounds n up to a power of two and maintains a lazy array for internal nodes.
  • •
    Typical use cases include range sum/min/max/GCD with point updates, and more advanced tasks like finding the first index where a prefix meets a predicate.

Prerequisites

  • →Binary trees and tree height — Understanding how a complete binary tree organizes elements and why operations take O(log n) is fundamental.
  • →Associativity and identity elements (monoids) — Segment trees require an associative merge and a neutral element to combine partial results correctly.
  • →Bitwise operations and integer division — Index arithmetic uses shifts, XOR, and division by two to navigate parents and siblings.
  • →Half-open intervals — Queries are implemented over [l, r), simplifying math and preventing off-by-one errors.
  • →Asymptotic analysis — To reason about performance guarantees like O(n) build and O(log n) updates/queries.

Detailed Explanation

Tap terms for definitions

01Overview

An iterative segment tree is a compact, non-recursive data structure for answering range queries (like sum, minimum, maximum, GCD) and supporting point updates efficiently. It lays out a full binary tree inside a flat array of size 2n: the original array elements sit as leaves at positions [n, 2n), and internal nodes occupy [1, n). Each internal node stores the result of merging its children using some associative operation (for example, sum or min). The key idea is to avoid recursion entirely. Updates and queries are implemented using loops and bitwise arithmetic on indices, yielding the same asymptotic complexity as recursive segment trees but with smaller constant-factor overhead.

With iterative trees, point updates take O(\log n) by writing to a leaf and walking upward to the root while recomputing parent nodes. Range queries on a half-open interval [l, r) also take O(\log n) by lifting two cursors l and r from the leaves toward their lowest common ancestors, merging contributions only when a cursor points to a node fully inside the query range. Building the tree from an array takes O(n) time by first copying leaves into [n, 2n) and then computing internal nodes from the bottom up.

While the classic iterative structure supports point updates and range queries, more complex operations like range updates with lazy propagation are also possible in an iterative style. This typically requires an additional lazy array and careful push/pull routines; many implementations simplify by rounding n up to a power of two to make segment sizes predictable.

02Intuition & Analogies

Imagine placing your array values as bricks on the bottom row of a pyramid. Each brick stores one number. Above every pair of adjacent bricks, you place another brick that stores their merged value (for example, their sum). You keep stacking levels until there is a single brick at the top that summarizes the entire array. This pyramid is your segment tree. Now, if you change one bottom brick, you only need to walk up along the path to the top, updating the few bricks that depended on it. That is why point updates are logarithmic.

For querying a range [l, r), picture two people starting at the bricks for positions l and r-1 on the bottom row. They climb up the pyramid toward the top. Each time one of them is currently at a "right child" or "left child" that perfectly covers a chunk still inside [l, r), they grab that brick’s value and move to the next parent. Otherwise, they move to the parent without taking anything. Eventually, they meet or cross, and the collected bricks exactly cover the range without overlap. Because the number of times they can step sideways is limited by the height of the pyramid, this also takes logarithmic time.

The iterative layout stores this pyramid in a single array. Instead of following pointers, you compute parents and siblings with simple index math: parent is i/2; left child is 2i; right child is 2i+1; sibling is i^1. Leaves are stored contiguously from index n to 2n-1 so you can map an original index i to its leaf as i+n. This compact layout enables fast constant-time navigation with simple loops, no recursion, and very predictable memory access patterns.

03Formal Definition

Let A be an array of length n over a set S equipped with an associative binary operation \(: S S S\) and an identity element e (i.e., a monoid). An iterative segment tree stores an array T of size 2n such that T[i] for i in [n, 2n) are leaves corresponding to A[i-n], and for internal nodes i in [1, n), we have \(T[i] = T[2i] T[2i+1]\). The root is T[1], which equals \( \). A point update at position p sets x (or applies x) by updating the leaf T[p+n] and then recomputing ancestors via i i/2 until , maintaining the invariant that each internal T[i] equals the merge of its children. A range query on [l, r) returns \( \) using two accumulators L and R initialized to e. While , if l is an odd index (a right child), L L T[l], l l+1; if r is an odd index, r r-1, R T[r] R; then set l l/2 and r r/2 . The final result is L R. Building T from A is done in O(n) by writing leaves T[i+n]=A[i] for ..n-1 and then computing internal nodes bottom-up: for down to 1, set T[i]=T[2i] T[2i+1]. When lazy propagation for range updates is required, an additional lazy array D of size n may be maintained with functions apply/push/build tailored to the chosen update and query operations, typically assuming n rounded up to a power of two to standardize segment sizes.

04When to Use

Use an iterative segment tree when you need many range queries with point updates, and the merge operation is associative: sums, minimum/maximum, bitwise OR/XOR, GCD, and many scoring functions. It is excellent for competitive programming where constant factors matter, since it avoids recursion overhead and has a small, cache-friendly memory footprint.

  • Range sum or range min with frequent point updates in O(\log n).
  • Problems that require fast prefix computations, like finding the first index where a running sum crosses a threshold; you can descend the tree iteratively in O(\log n).
  • Scenarios with a fixed-size array where building once in O(n) and then serving many queries is ideal.
  • When recursion depth might be a problem (very large n), the iterative version is robust and avoids stack limitations.

If you also need range updates (e.g., add v to all elements in [l, r)), consider an iterative lazy propagation approach. It is more complex to implement than the recursive version but can be very fast. A common tactic is to round n up to the next power of two to simplify segment lengths and lazy push logic.

If you only need prefix sums with point updates, a Fenwick tree (Binary Indexed Tree) may be simpler and slightly faster, but it cannot natively support min/max or custom associative operations as flexibly as a segment tree.

⚠️Common Mistakes

  • Off-by-one on query ranges: iterative segment trees conventionally use half-open intervals [l, r). Always test endpoints; querying [l, r] by mistake will overcount one element.
  • Forgetting associativity: the merge operation must be associative. If it isn’t, the tree can return incorrect results because the grouping of merges changes during queries.
  • Incorrect identity element: using the wrong neutral element (e.g., 0 for min instead of +\infty) silently breaks answers. For min, use +\infty; for max, use -\infty; for sum, use 0; for XOR, use 0; for AND, use all-ones.
  • Mixing 0-based and 1-based indices inside the tree: leaves should be at [n, 2n) and original indices map to i+n. Don’t accidentally place leaves starting at n-1 or index internal nodes from 0.
  • Forgetting to recompute ancestors after a point update: after writing a leaf, walk up with i >>= 1 and recompute T[i] from its children until i==1.
  • Assuming commutativity: two-pointer querying uses left and right accumulators; if the operation is not commutative (e.g., string concatenation), you must combine as L = L \oplus T[l] and R = T[r] \oplus R to preserve order.
  • Iterative lazy pitfalls: not rounding n to a power of two, miscomputing segment lengths when applying lazy values, or forgetting to push pending tags on boundary paths before a query. For range sums, applying a lazy add v to a node representing k elements must increase its stored sum by v*k, not just v.

Key Formulas

Parent Merge

Explanation: Each internal node stores the merge of its two children under an associative operation. This invariant defines how information aggregates up the tree.

Leaf Placement

Explanation: Array elements are stored as leaves in positions n..2n-1. This direct mapping allows O(1) access to a leaf for index arithmetic.

Index Arithmetic

Explanation: Parent, left child, right child, and sibling can all be computed from i using shifts and bitwise operations, enabling fast upward/downward moves without pointers.

Range Query Semantics

Explanation: The result of a range query equals the associative merge over all elements in the half-open interval [l, r). This defines correctness for queries.

Per-Operation Time

Explanation: Both point updates and range queries touch at most a constant number of nodes per tree level across \( n\) levels, yielding logarithmic time.

Build Time and Space

Explanation: Building from the array and storing the 2n cells (n leaves + n internal nodes) each take linear cost in n.

Two-Accumulator Invariant

Explanation: The query loop maintains partial results from the left and right boundaries. Merging them at the end gives the exact range aggregate in order.

Lazy Apply for Range Sum

Explanation: When adding v to all k elements of a node’s segment, its stored sum must increase by v times k. This is the key step in lazy range-add segment trees.

Power-of-Two Padding

Explanation: Rounding up to the next power of two simplifies segment lengths used by push/build in iterative lazy propagation.

Associativity Requirement

Explanation: Without associativity, re-grouping merges during queries can produce different results than the sequential definition over the range.

Complexity Analysis

Let n be the number of elements. The iterative segment tree stores 2n elements (n leaves and n internal nodes), so space is O(n). Building from an input array takes O(n) time: assigning leaves takes O(n), and a single bottom-up pass recomputes each internal node once. A point update changes one leaf and then recomputes its ancestors toward the root; there are at most \( n \) edges to traverse, and each level does O(1) work, giving O( n) time per update. A range query [l, r) uses two pointers that move upward; across all levels, each pointer performs at most two sideways steps (taking a full-cover node) before moving up. This leads to O( n) time per query. The constants are small because the implementation uses arithmetic on indices rather than recursive calls. For lazy propagation supporting range updates (e.g., range add) and range queries (e.g., range sum), we keep an additional lazy array of size O(n). Updates and queries remain O( n), but require careful push/build operations along the boundary paths to ensure correctness. Implementations frequently round n to N = 2^{ n } to standardize segment lengths for computing how a lazy tag affects a node’s stored value; space remains O(n), within a constant factor of the original. In practice, iterative segment trees are highly competitive on performance-critical tasks and are a staple in competitive programming for CF 1500–1900 level problems.

Code Examples

Basic Iterative Segment Tree for Range Sum and Point Update
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SegTreeSum {
5    int n;                 // number of elements
6    vector<long long> t;   // tree of size 2n
7
8    SegTreeSum(int n = 0) { init(n); }
9
10    void init(int n_) {
11        n = n_;
12        t.assign(2 * n, 0LL);
13    }
14
15    // Build from base array a (size n)
16    void build(const vector<long long>& a) {
17        init((int)a.size());
18        // Set leaves
19        for (int i = 0; i < n; ++i) t[n + i] = a[i];
20        // Build internal nodes
21        for (int i = n - 1; i > 0; --i) t[i] = t[i << 1] + t[i << 1 | 1];
22    }
23
24    // Point assignment: set A[p] = val
25    void set_point(int p, long long val) {
26        for (t[p += n] = val, p >>= 1; p > 0; p >>= 1) {
27            t[p] = t[p << 1] + t[p << 1 | 1];
28        }
29    }
30
31    // Point add: A[p] += delta
32    void add_point(int p, long long delta) {
33        int i = p + n;
34        t[i] += delta;
35        for (i >>= 1; i > 0; i >>= 1) t[i] = t[i << 1] + t[i << 1 | 1];
36    }
37
38    // Range sum on [l, r) (half-open)
39    long long query(int l, int r) const {
40        long long resL = 0, resR = 0; // identities for sum are 0
41        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
42            if (l & 1) resL += t[l++];
43            if (r & 1) resR += t[--r];
44        }
45        return resL + resR;
46    }
47};
48
49int main() {
50    ios::sync_with_stdio(false);
51    cin.tie(nullptr);
52
53    // Demo
54    vector<long long> a = {5, 2, 7, -3, 4, 6};
55    SegTreeSum st; st.build(a);
56
57    cout << st.query(0, 6) << "\n";   // sum of all -> 21
58    cout << st.query(1, 4) << "\n";   // sum on [1,4) -> 2 + 7 + (-3) = 6
59
60    st.add_point(3, 5);                // A[3] += 5 -> now A[3] = 2
61    cout << st.query(1, 4) << "\n";   // [1,4): 2 + 7 + 2 = 11
62
63    st.set_point(0, 10);               // A[0] = 10
64    cout << st.query(0, 2) << "\n";   // [0,2): 10 + 2 = 12
65
66    return 0;
67}
68

This is the canonical 2n iterative segment tree for range sums. Leaves are at indices [n, 2n). Point updates rewrite a leaf and pull up along the path to the root. Range queries [l, r) use two accumulators moving upward. It avoids recursion and is very fast in practice.

Time: O(log n) per update/query; O(n) buildSpace: O(n) additional space (2n cells)
Generic Iterative Segment Tree (Monoid) for Range-Min Query
1#include <bits/stdc++.h>
2using namespace std;
3
4template<class T, class Op>
5struct SegTree {
6    int n;
7    vector<T> t;
8    T id;     // identity element
9    Op op;    // associative operation: T x T -> T
10
11    SegTree(int n=0, T id=T(), Op op=Op()) : n(0), id(id), op(op) { init(n); }
12
13    void init(int n_) {
14        n = n_;
15        t.assign(2*n, id);
16    }
17
18    void build(const vector<T>& a) {
19        init((int)a.size());
20        for (int i = 0; i < n; ++i) t[n + i] = a[i];
21        for (int i = n - 1; i > 0; --i) t[i] = op(t[i<<1], t[i<<1|1]);
22    }
23
24    void set_point(int p, T val) {
25        for (t[p += n] = val, p >>= 1; p > 0; p >>= 1)
26            t[p] = op(t[p<<1], t[p<<1|1]);
27    }
28
29    // Range query on [l, r)
30    T query(int l, int r) const {
31        T resL = id, resR = id;
32        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
33            if (l & 1) resL = op(resL, t[l++]);      // left-to-right
34            if (r & 1) resR = op(t[--r], resR);      // right-to-left preserves order
35        }
36        return op(resL, resR);
37    }
38};
39
40// Example op for range minimum
41struct MinOp {
42    long long operator()(long long a, long long b) const { return min(a, b); }
43};
44
45int main() {
46    ios::sync_with_stdio(false);
47    cin.tie(nullptr);
48
49    const long long INF = (1LL<<60);
50    vector<long long> a = {7, 3, 9, 1, 5, 8};
51
52    SegTree<long long, MinOp> st; st.id = INF; st.op = MinOp(); st.build(a);
53
54    cout << st.query(0, 6) << "\n"; // min over all: 1
55    cout << st.query(1, 4) << "\n"; // min on [1,4): min(3,9,1) = 1
56
57    st.set_point(3, 10);             // set A[3]=10
58    cout << st.query(1, 4) << "\n"; // min(3,9,10) = 3
59
60    return 0;
61}
62

This template implements an iterative segment tree over any monoid (associative op + identity). The example instantiates it for RMQ (range minimum) with identity +∞. The query uses two accumulators to preserve order for potentially non-commutative ops.

Time: O(log n) per update/query; O(n) buildSpace: O(n)
Iterative Lazy Propagation: Range Add, Range Sum (n rounded to power of two)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SegTreeLazyAddSum {
5    int n0;        // original size
6    int N;         // power-of-two size >= n0
7    int H;         // height = log2(N)
8    vector<long long> t; // sums
9    vector<long long> d; // lazy tags (pending adds) for internal nodes [1..N-1]
10
11    SegTreeLazyAddSum(int n=0) { init(n); }
12
13    static int next_pow2(int n) {
14        int N = 1; while (N < n) N <<= 1; return N;
15    }
16
17    void init(int n) {
18        n0 = n;
19        N = max(1, next_pow2(n0));
20        H = 0; while ((1 << H) < N) ++H;
21        t.assign(2 * N, 0LL);
22        d.assign(N, 0LL);
23    }
24
25    void build(const vector<long long>& a) {
26        init((int)a.size());
27        for (int i = 0; i < (int)a.size(); ++i) t[N + i] = a[i];
28        for (int i = N - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
29    }
30
31    // Apply +val to node p which represents k leaves
32    void apply(int p, long long val, int k) {
33        t[p] += val * k;
34        if (p < N) d[p] += val; // store lazy at internal nodes
35    }
36
37    // Push all pending tags on path to node p (leaf index in [N,2N))
38    void push(int p) {
39        for (int s = H; s > 0; --s) {
40            int i = p >> s; // ancestor at depth s
41            if (d[i] != 0) {
42                long long v = d[i];
43                apply(i<<1, v, 1 << (s-1));
44                apply(i<<1|1, v, 1 << (s-1));
45                d[i] = 0;
46            }
47        }
48    }
49
50    // Recompute ancestors of node p (leaf index in [N,2N))
51    void build_up(int p) {
52        int k = 1;
53        for (p >>= 1; p > 0; p >>= 1) {
54            k <<= 1;
55            t[p] = t[p<<1] + t[p<<1|1] + d[p] * 1LL * k;
56        }
57    }
58
59    // Range add on [l, r)
60    void range_add(int l, int r, long long val) {
61        if (l >= r) return;
62        int l0 = l + N, r0 = r - 1 + N; // for push/build boundaries
63        push(l0);
64        push(r0);
65        int k = 1;
66        for (l += N, r += N; l < r; l >>= 1, r >>= 1, k <<= 1) {
67            if (l & 1) apply(l++, val, k);
68            if (r & 1) apply(--r, val, k);
69        }
70        build_up(l0);
71        build_up(r0);
72    }
73
74    // Range sum on [l, r)
75    long long range_sum(int l, int r) {
76        if (l >= r) return 0;
77        int l0 = l + N, r0 = r - 1 + N;
78        push(l0);
79        push(r0);
80        long long resL = 0, resR = 0;
81        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
82            if (l & 1) resL += t[l++];
83            if (r & 1) resR += t[--r];
84        }
85        return resL + resR;
86    }
87};
88
89int main() {
90    ios::sync_with_stdio(false);
91    cin.tie(nullptr);
92
93    vector<long long> a = {1, 2, 3, 4, 5};
94    SegTreeLazyAddSum st; st.build(a);
95
96    cout << st.range_sum(0, 5) << "\n"; // 15
97    st.range_add(1, 4, 10);              // add 10 to indices 1,2,3
98    cout << st.range_sum(0, 5) << "\n"; // 15 + 30 = 45
99    cout << st.range_sum(2, 5) << "\n"; // (3+10) + (4+10) + 5 = 32
100
101    st.range_add(0, 5, -2);             // subtract 2 everywhere
102    cout << st.range_sum(0, 2) << "\n"; // (1-2) + (2+10-2) = -1 + 10 = 9
103
104    return 0;
105}
106

This is a fully iterative lazy segment tree supporting range add and range sum. We round n up to a power of two (N) so each node covers exactly a power-of-two number of leaves. The lazy array d stores pending additions at internal nodes. push clears pending tags along boundary paths before operations; build_up recomputes ancestors after updates.

Time: O(log n) per range update/query; O(n) buildSpace: O(n)
Finding the First Index with Prefix Sum ≥ X (Iterative Descent)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct SegTreeSum {
5    int n; vector<long long> t;
6    void build(const vector<long long>& a) {
7        n = (int)a.size(); t.assign(2*n, 0LL);
8        for (int i = 0; i < n; ++i) t[n+i] = a[i];
9        for (int i = n-1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
10    }
11    void set_point(int p, long long v) {
12        for (t[p+=n]=v, p>>=1; p; p>>=1) t[p]=t[p<<1]+t[p<<1|1];
13    }
14    long long sum(int l, int r) const {
15        long long L=0,R=0; for (l+=n,r+=n; l<r; l>>=1,r>>=1){ if(l&1)L+=t[l++]; if(r&1)R+=t[--r]; } return L+R;
16    }
17    // Return the smallest idx such that sum(0, idx+1) >= x; return -1 if not found.
18    int first_prefix_at_least(long long x) const {
19        if (n == 0 || t[1] < x) return -1; // total sum too small
20        int p = 1; // start at root
21        while (p < n) {
22            if (t[p<<1] >= x) p = p<<1;     // go left if left sum is enough
23            else { x -= t[p<<1]; p = p<<1|1; } // otherwise go right after subtracting left
24        }
25        return p - n; // leaf index
26    }
27};
28
29int main(){
30    ios::sync_with_stdio(false);
31    cin.tie(nullptr);
32
33    vector<long long> a = {2, 1, 3, 2, 5};
34    SegTreeSum st; st.build(a);
35
36    cout << st.first_prefix_at_least(3) << "\n";  // prefix >= 3 is at idx 1 (2+1)
37    cout << st.first_prefix_at_least(6) << "\n";  // idx 2 (2+1+3)
38    cout << st.first_prefix_at_least(20) << "\n"; // -1 (not found)
39
40    st.set_point(0, 10);
41    cout << st.first_prefix_at_least(8) << "\n";  // idx 0 now (10)
42
43    return 0;
44}
45

Using the sum segment tree, we can descend from the root to find the first index where the prefix sum reaches a target. At each step, we check whether the left child already has enough sum; if not, we subtract it and go right.

Time: O(log n) per searchSpace: O(n)