Segment Trees Explained — Build, Query, Update and Lazy Propagation

Range queries are everywhere. Stock price analytics, game leaderboards, genomic data analysis, database index scans — all of them need to answer questions like 'what is the maximum value between index 3 and index 47?' millions of times per second. If your data never changed, a prefix-sum array would suffice. But real data does change, and that's where the naive approaches fall apart embarrassingly fast.

The brute-force fix — loop over the range every time — costs O(n) per query. A prefix-sum array costs O(1) per query but O(n) per update because you have to recompute everything downstream. Neither is acceptable when you're handling millions of operations on an array of 100,000 elements. You need a data structure that keeps both query time and update time logarithmic, simultaneously. That's the exact gap Segment Trees were designed to close.

By the end of this article you'll be able to build a Segment Tree from scratch, handle point updates, execute range queries, and — the part that trips up most developers — implement lazy propagation for range updates. You'll also understand the memory layout internals, know exactly when a Segment Tree is and isn't the right tool, and walk into any interview prepared to discuss the tradeoffs confidently.

What is Segment Tree? — Plain English

A Segment Tree is a data structure built on an array that allows two operations efficiently: range queries (e.g., sum, minimum, or maximum over any subarray) and point updates (change one element). A naive approach takes O(n) per range query and O(1) per update. A prefix sum array takes O(1) per query but O(n) per update. A Segment Tree achieves O(log n) for both.

Think of it as a binary tree where each leaf stores one array element, and each internal node stores the combined result (sum, min, max) of its children's ranges. The root covers the entire array. Querying a range means combining at most O(log n) nodes. Updating one element means propagating the change up O(log n) ancestors.

How Segment Tree Works — Step by Step

Build (O(n)): 1. Allocate a tree array of size 4n (safe upper bound for a 1-indexed tree). 2. Build recursively: tree[node] = combine(tree[2node], tree[2*node+1]). 3. Leaves (when left==right) store the original array values.

Point Update (O(log n)): 1. Start at the leaf for the updated index. Update the leaf value. 2. Walk back to the root, recomputing each ancestor as combine(left child, right child).

Range Query (O(log n)): 1. If current node's range is completely outside the query range: return identity (0 for sum, +inf for min). 2. If completely inside: return tree[node]. 3. Otherwise: query both children, return combine(left result, right result).

The combine function determines what the tree computes: sum, minimum, maximum, GCD, etc.

Worked Example — Tracing the Algorithm

Array: [1, 3, 5, 7, 9, 11] (indices 0-5). Build a sum segment tree.

Tree structure (node: range -> value): Node 1: [0,5] -> 36 (sum of all) Node 2: [0,2] -> 9 Node 3: [3,5] -> 27 Node 4: [0,1] -> 4 Node 5: [2,2] -> 5 Node 6: [3,4] -> 16 Node 7: [5,5] -> 11 Node 8: [0,0] -> 1 Node 9: [1,1] -> 3 Node 12: [3,3] -> 7 Node 13: [4,4] -> 9

Query sum(1, 4) — range [1,4]: Node 1 [0,5]: partial. Go to children. Node 2 [0,2]: partial. Go to children. Node 4 [0,1]: partial. Go to children. Node 8 [0,0]: outside [1,4]. Return 0. Node 9 [1,1]: inside [1,4]. Return 3. Node 5 [2,2]: inside [1,4]. Return 5. Node 3 [3,5]: partial. Go to children. Node 6 [3,4]: inside [1,4]. Return 16. Node 7 [5,5]: outside [1,4]. Return 0. Result: 0+3+5+16+0 = 24. Correct: arr[1]+arr[2]+arr[3]+arr[4] = 3+5+7+9 = 24.

Update arr[2] = 10 (was 5): Update leaf Node 5: 5->10. Update Node 2: 9->14. Update Node 1: 36->41. Done. O(log n) = 3 operations.

Implementation

The tree is stored in a 1-indexed array of size 4n. Node i covers a range; its children are at 2i and 2*i+1. build fills leaves with array values and internal nodes with the sum of children. update recurses to the target leaf and propagates the new sum upward. query returns the identity (0 for sum) when the current range is outside the query, returns the stored value when fully inside, and combines children recursively for partial overlaps — visiting at most O(log n) nodes per call.

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self._build(arr, 0, self.n - 1, 1)

    def _build(self, arr, l, r, node):
        if l == r:
            self.tree[node] = arr[l]
            return
        mid = (l + r) // 2
        self._build(arr, l, mid, 2*node)
        self._build(arr, mid+1, r, 2*node+1)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def update(self, idx, val, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if l == r:
            self.tree[node] = val
            return
        mid = (l + r) // 2
        if idx <= mid: self.update(idx, val, l, mid, 2*node)
        else:           self.update(idx, val, mid+1, r, 2*node+1)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, ql, qr, l=None, r=None, node=1):
        if l is None: l, r = 0, self.n - 1
        if qr < l or r < ql: return 0  # out of range
        if ql <= l and r <= qr: return self.tree[node]  # fully inside
        mid = (l + r) // 2
        return self.query(ql, qr, l, mid, 2*node) + self.query(ql, qr, mid+1, r, 2*node+1)

arr = [1, 3, 5, 7, 9, 11]
st  = SegmentTree(arr)
print('sum(1,4):', st.query(1, 4))   # 3+5+7+9 = 24
st.update(2, 10)                      # arr[2] = 10
print('sum(1,4) after update:', st.query(1, 4))  # 3+10+7+9 = 29

Frequently Asked Questions