Iterative Segment Trees

April 2026 · 18 min read

Everything we’ve covered so far used recursive segment trees: top-down build, top-down query, top-down update. They’re intuitive and flexible (especially for lazy propagation). But there’s an entirely different way to implement segment trees — iteratively, from the bottom up — that’s faster, uses less memory, and requires zero recursion.

This post covers the iterative segment tree from scratch: its different memory layout, why it works, how every operation works, and when to prefer it over the recursive version.

A Different Memory Layout

Recursive layout recap

In the recursive segment tree, we use a 1-indexed array of size 4n. The root is at index 1, and we split ranges recursively. For non-power-of-2 array sizes, some slots go unused — hence the 4n worst-case allocation.

The iterative layout

The iterative segment tree uses a completely different layout:

1. Pad n to the next power of 2. If the original array has 5 elements, pad to 8. If it has 8, leave it. This ensures the tree is a perfect binary tree with no gaps.
2. Allocate exactly 2n slots (where n is the padded size). That’s it — no wasted space.
3. Leaves sit at indices [n, 2n−1]. Internal nodes sit at [1, n−1]. Index 0 is unused.

“But you said always use 4n!”

That rule is for the recursive layout, where n can be anything and the recursive splitting leaves gaps in the array. The iterative layout is different: you pad n to a power of 2 first, making the tree perfect. A perfect binary tree with n leaves has exactly n − 1 internal nodes, totaling 2n − 1 nodes. With index 0 unused, 2n slots is tight and exact.

Why leaves at [n, 2n−1]?

In a perfect binary tree with n leaves, the leaf level is exactly level log2(n). In 1-indexed BFS numbering, level d starts at index 2d. Since n = 2d, the leaves start at index n. The i-th array element (0-indexed) maps to tree index n + i.

This means: to go from array index to tree index, just add n. To go back, subtract n. No recursion needed to find a leaf.

Iterative Build

Building is two loops:

void build(const vector<int>& arr, vector<int>& tree, int n) {
    // Step 1: Copy leaves into positions [n, 2n-1]
    for (int i = 0; i < (int)arr.size(); i++)
        tree[n + i] = arr[i];
    // Remaining leaves (padding) stay 0 (identity for sum)

    // Step 2: Fill internal nodes bottom-up
    for (int i = n - 1; i >= 1; i--)
        tree[i] = tree[2 * i] + tree[2 * i + 1];
}

That’s it. No recursion, no range parameters, no base case checks.

Why this works

• Step 1: Leaves are just the array values, placed directly at their tree positions.
• Step 2: We iterate from n−1 down to 1. Node i’s children are 2i and 2i+1 (both have larger indices). Since we iterate in decreasing order, both children are already filled when we compute their parent.

Walkthrough: Build for [1, 3, 5, 7]

3 iterations. The recursive build for the same array takes 10 function calls.

Build with non-power-of-2 sizes

If the original array has 5 elements, pad n to 8:

int orig = arr.size();
int n = 1;
while (n < orig) n <<= 1;  // next power of 2

vector<int> tree(2 * n, 0);  // identity-filled
for (int i = 0; i < orig; i++)
    tree[n + i] = arr[i];
// tree[n+5], tree[n+6], tree[n+7] stay 0 (sum identity)

for (int i = n - 1; i >= 1; i--)
    tree[i] = tree[2 * i] + tree[2 * i + 1];

The padding slots contain the identity value (0 for sum, ∞ for min, −∞ for max). They don’t affect query results.

Iterative Point Update

To update arr[pos], go directly to its leaf, update it, then walk up to the root fixing every ancestor:

void update(vector<int>& tree, int n, int pos, int val) {
    pos += n;               // jump to leaf
    tree[pos] = val;        // set new value (or += val for add)

    // Walk up, recomputing each parent
    for (pos >>= 1; pos >= 1; pos >>= 1)
        tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
}

Walkthrough: update(2, 10) on [1, 3, 5, 7]

Set arr[2] = 10. Leaf is at tree index 4 + 2 = 6.

Exactly log2(n) parent updates. O(log n).

Iterative Range Query

This is the cleverest part. Instead of recursing top-down and checking three cases, we use a two-pointer bottom-up walk.

int query(const vector<int>& tree, int n, int l, int r) {
    int res = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res += tree[l++];   // l is a right child
        if (r & 1) res += tree[--r];   // include left sibling of r
    }
    return res;
}

Step-by-step: How the two-pointer query works

We convert [l, r] (inclusive, 0-indexed) into tree indices and use a half-open interval [l, r) internally. Then we walk both pointers upward simultaneously:

1. If l is odd (a right child): its parent’s range extends left beyond our query. We can’t use the parent — so we take tree[l] alone and advance l one step right (now it’s aligned to a left child).
2. If r is odd (a right child): the node at r−1 is the last node still inside our range. Decrement r and take tree[r].
3. Move to parents: l >>= 1; r >>= 1.
4. Repeat until l ≥ r.

Why “is odd = right child”?

In the iterative layout:

• Left child of parent p = 2p (always even)
• Right child of parent p = 2p + 1 (always odd)

So l & 1 checks if l is a right child. If it is, its parent covers elements outside our query range on the left side. We can’t “go through” the parent, so we collect this node individually and move l to the next node (which will be a left child of some other parent, properly aligned).

Walkthrough: query(1, 3) on [1, 3, 5, 7]

We want sum(arr[1..3]) = 3 + 5 + 7 = 15.

Tree (n=4): [_, 16, 4, 12, 1, 3, 5, 7]

2 iterations, 2 additions. No recursion, no case-checking.

Walkthrough: query(0, 1) on [1, 3, 5, 7]

We want sum(arr[0..1]) = 1 + 3 = 4.

This time the r pointer did the collecting. Both pointers can contribute — they handle the left and right boundaries independently.

Interactive Walkthrough

Complexity Analysis

Same asymptotic complexity as the recursive version, but with much smaller constants:

• No function call overhead (no recursion stack frames)
• No range parameter passing (no start/end/l/r at each call)
• Simple bit operations (& 1, >>= 1) instead of comparisons
• Better cache locality (sequential array access patterns)

In competitive programming benchmarks, iterative segment trees are typically 2–3× faster than recursive ones.

Complete Implementation

class IterativeSegTree {
    int n;
    vector<int> tree;

public:
    IterativeSegTree(const vector<int>& arr) {
        n = 1;
        while (n < (int)arr.size()) n <<= 1;
        tree.assign(2 * n, 0);

        for (int i = 0; i < (int)arr.size(); i++)
            tree[n + i] = arr[i];
        for (int i = n - 1; i >= 1; i--)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    void update(int pos, int val) {
        pos += n;
        tree[pos] = val;
        for (pos >>= 1; pos >= 1; pos >>= 1)
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1];
    }

    int query(int l, int r) {
        int res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += tree[l++];
            if (r & 1) res += tree[--r];
        }
        return res;
    }
};

The entire class is under 25 lines. Compare to the recursive version which needs separate build/query/update functions with 5+ parameters each.

Adapting for Other Operations

Swap the merge and identity to use min, max, GCD, XOR, etc.:

Recursive vs. Iterative: When to Use Which

Common Mistakes

• Forgetting to pad n: If n isn’t a power of 2 and you don’t pad, the tree layout breaks. Always round up.
• Wrong identity for padding: Padding slots must contain the identity (0 for sum, ∞ for min). Using 0 for a min-tree silently returns wrong answers.
• Off-by-one in query: The query uses r += n + 1 (not r += n) because the interval is half-open internally. Missing the +1 excludes the last element.
• Updating the wrong direction: After changing a leaf, walk up (pos >>= 1), not down. Each parent is recomputed from its two children.
• Using iterative layout with recursive code: The two layouts are incompatible. Don’t mix 4n allocation with pos += n leaf indexing.

Practice Problems

All problems solvable with the recursive segment tree work with the iterative version too. These are good ones to practice the iterative template specifically:

• CSES — Dynamic Range Sum Queries — Point update + range sum. The perfect first problem for iterative seg tree.
• CSES — Dynamic Range Minimum Queries — Same but with min. Tests identity value handling.
• LeetCode 307 — Range Sum Query Mutable — Classic point update + range sum.
• CSES — Static Range Sum Queries — No updates, but good for testing query correctness.
• Codeforces 339D — Xenia and Bit Operations — Alternating OR/XOR by level. Tests iterative update with non-standard merge.

Summary

• The iterative segment tree uses a different layout: pad n to power of 2, leaves at [n, 2n−1], allocate 2n.
• Build: Copy leaves, then one loop from n−1 down to 1. O(n).
• Update: Jump to leaf (pos + n), walk up recomputing parents. O(log n).
• Query: Two-pointer bottom-up walk. Odd index = right child = collect individually. O(log n).
• Same asymptotic complexity as recursive, but 2–3× faster in practice.
• Use recursive when you need lazy propagation. Use iterative for speed.