Segment Trees: The Matrix of Range Queries

The Quest Begins (The “Why”)

Ever been stuck solving a problem that asks for the sum (or min, max, gcd…) of a sub‑array a hundred times, only to watch your brute‑force loop crawl to a halt? I was there last week, prepping for a backend interview. The interviewer tossed a classic:

Given an array a[0…n‑1], support two operations:

1. Update – change a[i] to a new value.
2. Query – return the sum of a[l…r] (inclusive).

Naïvely, each query is O(r‑l+1). With m queries that becomes O(n·m) – unacceptable when n and m are both 10⁵. I felt like Neo staring at the Matrix code, knowing there had to be a deeper pattern but not seeing it yet.

That frustration sparked my quest: find a data structure that turns both update and query into logarithmic time while keeping the build linear. Enter the segment tree – the “bullet‑time” of range queries.

The Revelation (The Insight)

So why does a segment tree work? Imagine you want to answer “what’s the sum of a segment?” You could pre‑compute every possible segment, but that’s O(n²) space – crazy. The trick is to reuse work.

A segment tree is a binary tree where each node stores the answer for a specific interval. The root covers [0, n‑1]. Its left child covers [0, mid], right child covers [mid+1, n‑1], and so on, until leaves represent single elements.

Key insight: Any query interval [l, r] can be expressed as a disjoint union of O(log n) node intervals. Why? Because as we walk down the tree, whenever the current node’s interval is completely inside [l, r] we take its stored value and stop recursing deeper; otherwise we split and continue. At each level we add at most two nodes (the parts that “stick out”), and there are only log₂ n levels.

Similarly, an update touches only the nodes on the path from the leaf to the root – again O(log n). The build phase simply fills leaves with the original array values and then bubbles up: each internal node = combine(left child, right child). That’s a single pass over 2·n nodes → O(n) time and O(n) space.

The “combine” operation is whatever the problem needs: addition for sum, min for range minimum, gcd for range gcd, etc. As long as it’s associative and we have an identity element, the segment tree fits.

Wielding the Power (Code & Examples)

Let’s see the spell in action. Below is a clean, iterative segment tree for range sum with point updates (the classic “binary indexed tree” sibling, but we’ll stick to the tree form for clarity).

Naïve baseline (the struggle)

def build_naive(arr):
    return arr                     # O(1) space, but queries are O(n)

def query_naive(arr, l, r):
    return sum(arr[l:r+1])        # O(r-l+1)

def update_naive(arr, idx, val):
    arr[idx] = val                # O(1)

Fine for tiny inputs, but hopeless at scale.

The segment tree victory

class SegTree:
    """Iterative segment tree for range sum."""
    def __init__(self, data):
        self.n = len(data)
        # size = next power of two >= n
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        # load leaves
        self.tree[self.size:self.size + self.n] = data
        # build internal nodes
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

    def update(self, idx, value):
        """Set a[idx] = value."""
        pos = self.size + idx
        self.tree[pos] = value
        # go up
        while pos > 1:
            pos >>= 1
            self.tree[pos] = self.tree[pos << 1] + self.tree[pos << 1 | 1]

    def query(self, l, r):
        """Return sum on [l, r] inclusive."""
        l += self.size
        r += self.size + 1   # make r exclusive
        res = 0
        while l < r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                res += self.tree[r]
            l >>= 1
            r >>= 1
        return res

Why this feels like a cheat code:

• The while loop in query walks up the tree, adding at most two nodes per level → O(log n).
• update touches exactly the nodes on the root‑to‑leaf path → also O(log n).
• Construction is a single bottom‑up pass → O(n).

Common traps (the “bosses” to avoid)

1. Off‑by‑one on the leaf offset – forgetting that leaves start at self.size leads to reading/writing the wrong indices.
2. Not making the right bound exclusive in the query loop – if you treat r as inclusive you’ll either miss the last element or double‑count.
3. Using recursion without tail‑call optimisation in languages that penalise deep stacks (Python’s recursion limit ~1000). The iterative version sidesteps that entirely.

Two interview‑style problems solved

Problem 1 – Range Sum Query (LeetCode 307)

Input: nums = [1,3,5]

Operations: sumRange(0,2) → 9, update(1,2), sumRange(0,2) → 8

Our SegTree handles both in O(log n) per call, passing all test cases with ease.

Problem 2 – Range Minimum Query (Classic RMQ)

Same structure, just change the combine to min and set identity to +∞.

self.tree[i] = min(self.tree[i << 1], self.tree[i << 1 | 1])

Now query(l,r) returns the minimum in O(log n). Many interviewers love to ask “can you do better than O(n) per query?” – the segment tree is the answer.

Why This New Power Matters

With a segment tree in your toolbox you stop fearing any problem that talks about “range … queries”. You can:

• Build a dynamic order statistic tree (just store counts).
• Solve range gcd, range xor, or even range max subarray sum (by storing four values per node).
• Plug it into a lazy propagation variant for range updates – the same tree, just a little extra magic.

In short, you go from “I’ll loop over the array each time” to “I’ll query in logarithmic time and sleep peacefully knowing my solution scales”. That shift feels like unlocking a new ability in a RPG – suddenly the boss that once seemed unbeatable is just another XP gain.

Your Turn

Grab your favourite language, implement the iterative segment tree for range sum, then twist it to solve a range product modulo 10⁹+7. Try adding lazy propagation for range increments – it’s a natural next step.

What’s the first range‑query problem you’ll conquer with this new spell? Drop your solution or a question in the comments; I’d love to see how you wield the power!

---

Happy coding, and may your queries always be logarithmic!