Segment Trees: My Go-To Pattern for Lightning-Fast Range Queries

The Pain Point That Changed Everything

I once blew an interview because I answered range-sum queries with a naive sum(arr[L:R+1]) call. The interviewer then dropped the bomb: 10^5 queries on a 10^5-length array. My O(n) per query approach would have needed up to 10^10 operations. Time to learn segment trees, fast.

Why Segment Trees Work

Segment trees exploit two key ideas:

1. Associativity allows combining. If you know the summary of [L, M] and [M+1, R], you can merge them in one operation (like sum_left + sum_right).
2. Query ranges cover O(log n) nodes. Any query walks down the tree, collecting fully-contained nodes and skipping irrelevant ones.

The result? O(log n) per query after an O(n) build. It's divide-and-conquer made practical.

The Code That Actually Works

Here's my clean, iterative-friendly implementation that I keep in my snippet library:

class SegTree:
    def __init__(self, data, func=sum):
        """Build a segment tree for `data` using associative `func`."""
        self.n = len(data)
        self.func = func
        # size of the tree array (next power of two * 2)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        # place leaves
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # build parents bottom-up
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        """Return func over data[l:r] (inclusive)."""
        res_left = res_right = 0  # identity for sum; adjust for min/max/etc.
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                res_left = self.func(res_left, self.tree[l])
                l += 1
            if r % 2 == 0:
                res_right = self.func(self.tree[r], res_right)
                r -= 1
            l >>= 1
            r >>= 1
        return self.func(res_left, res_right)

    def update(self, idx, value):
        """Set arr[idx] = value and refresh the tree."""
        pos = self.size + idx
        self.tree[pos] = value
        pos >>= 1
        while pos:
            self.tree[pos] = self.func(self.tree[2 * pos], self.tree[2 * pos + 1])
            pos >>= 1

Why this version? The flat-array layout with children at 2*i and 2*i+1 makes it cache-friendly and easy to reason about. The build step walks from leaves upward, guaranteeing each parent holds the func of its children.

When to Reach for This Pattern

Segment trees shine whenever you need:

• Range sum, min, max, or GCD queries with point updates
• Associative operations where combining two results is cheap
• Frequent queries (think 10^4+) on moderately sized arrays

The trade-off? Slightly more complex code than a prefix-sum array, but prefix sums break the moment you need updates. Segment trees handle both cleanly.

My Config Tips

• Default identity: Use 0 for sum, float('inf') for min, float('-inf') for max
• Memory: The tree array is 2 * next_power_of_two(n), so for n=10^5 it's about 262144 elements
• Custom operations: Just pass any associative function to func — works for XOR, product, or even custom reducers

The Bigger Picture

This is one of those patterns that pays dividends across languages. Whether I'm solving competitive programming problems or optimizing a production service with frequent range lookups, the segment tree structure stays the same. It's a foundational technique that turns "too slow" into "instant."

If you're prepping for interviews or just tired of timing out on range queries, this is worth memorizing. The iterative implementation above is production-ready and handles edge cases gracefully.