Segment Trees

You have a series of 100,000 values — one-minute returns, say — and you keep asking for the sum over arbitrary windows. If the data never changes, Prefix Sums solve this outright: precompute running totals once and every window sum becomes one subtraction, $O(1)$.

Now let one value change. A late correction arrives and minute 40,312 is revised. Every prefix sum after that point is now wrong, and rebuilding them costs $O(n)$. Do that a few thousand times and the "fast" solution is the slowest thing in your pipeline. The opposite extreme — no precomputation, just loop over the window — makes updates free but each query $O(n)$.

A segment tree refuses the trade. It makes both operations $O(\log n)$.

The idea: a pyramid of partial answers

Think of a knockout tournament drawn upside down. The bottom row is your raw data. Each node one level up stores the combined result for the two children below it — their sum, or their minimum, whichever aggregate you care about. The root, at the top, holds the aggregate of everything.

Two properties make this work. First, any range you ask about can be cut into a handful of nodes that already exist: a query over positions 1 to 6 in an eight-element array is not seven separate lookups, it is a couple of pre-aggregated blocks plus a couple of leaves. There are at most two such blocks per level, so a query touches $O(\log n)$ nodes. Second, when one leaf changes, only the nodes on the path from that leaf to the root contain it, so an update fixes exactly $\log_2 n$ values.

$$\text{build } O(n), \quad \text{query } O(\log n), \quad \text{update } O(\log n), \quad \text{space } O(n)$$

In words: building the pyramid once costs a single linear pass, and after that both reading a range and changing a point cost about $\log_2 n$ steps — 17 steps for 100,000 elements.

Worked example: query and update

Take [1, 2, 5, 3, 4, 5, 7, 4] and build the sum tree above. Ask for the sum over positions 2 to 7. Start at the root [0,7]: it is not fully inside the query, so split. [0,3] overlaps partially, split again; [0,1] is entirely outside, discard it; [2,3] = 8 is entirely inside, take it whole. Back on the right, [4,7] = 20 is entirely inside, take it whole. Total 8 + 20 = 28 from two node reads.

Now update position 5 from 5 to 9, a change of +4. Only the nodes containing position 5 are affected: leaf 5 → 9, then [4,5]: 9 → 13, then [4,7]: 20 → 24, then the root 31 → 35. Three internal nodes touched, and every future query is instantly correct.

class SegTree:                      # build O(n), query/update O(log n)
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = a
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2*i] + self.t[2*i + 1]

    def update(self, i, val):       # walk leaf -> root, log n parents
        i += self.n
        self.t[i] = val
        while i > 1:
            i //= 2
            self.t[i] = self.t[2*i] + self.t[2*i + 1]

    def query(self, lo, hi):        # sum over [lo, hi)
        res, lo, hi = 0, lo + self.n, hi + self.n
        while lo < hi:
            if lo & 1: res += self.t[lo]; lo += 1
            if hi & 1: hi -= 1; res += self.t[hi]
            lo //= 2; hi //= 2
        return res

Worked example: the same tree, minimum instead of sum

Change the combine step from + to min and rebuild on the same array. The leaves are unchanged; [0,1] now stores min(1,2) = 1, [2,3] stores 3, [4,5] stores 4, [6,7] stores 4, and the root stores 1. Ask for the minimum over positions 2 to 7 and you take the same two nodes as before: min([2,3], [4,7]) = min(3, 4) = 3. Nothing about the traversal changed — only the operator did.

Where it shows up

Interviewers use segment trees for "range sum with updates", "range minimum query", counting inversions during a merge, and the harder skyline and rectangle-area problems. Saying "prefix sums, unless there are updates, in which case a segment tree" is often the whole answer they want.

On a desk the pattern is everywhere once you see it. Rolling statistics over a tick stream where late corrections rewrite past bars; aggregate depth in an order book across a band of price levels while individual levels change every millisecond; risk aggregation over a book bucketed by sector or maturity, where one position moves and you need the desk total immediately; and VWAP over an arbitrary intraday window rather than a fixed one. In each case the alternative is recomputing a linear pass per update, and at market data rates that is exactly the budget you do not have.