Segment trees

What this chapter covers

Here's a problem a plain array can't solve well: you have a list of numbers, and you need to repeatedly ask "what's the sum of everything between position i and j?" while also changing individual elements. Keep the raw values and each range query costs O(n). Precompute prefix sums and queries drop to O(1) — but now every update forces an O(n) rebuild. You're stuck choosing which operation to make slow. The segment tree refuses the choice: it's a tree of range aggregates that makes both the range query and the point update O(log n). This chapter builds it, watches a query shatter into O(log n) precomputed pieces, and measures it beating both array approaches on a mixed workload.

A bit of history

Segment trees come from computational geometry. In the 1970s, as researchers built algorithms for problems like "which of these line segments contain a given point," Jon Bentley and others developed tree structures over ranges of a coordinate axis — the segment tree and its relatives (interval trees, range trees). The core idea, decomposing any interval into a logarithmic number of precomputed canonical pieces, turned out to be enormously general, applying to any associative aggregate over ranges, not just geometry. It found a second life in competitive programming from the 1990s onward, where "range query with updates" is a staple, and the segment tree (with its lazy-propagation extension) became the standard heavy artillery. It's less a single algorithm than a template: pick an associative operation — sum, min, max, gcd — and the same tree answers range queries and point updates for it in O(log n).

The intuition

Build a binary tree over the array's positions. The root covers the whole array and stores the aggregate — say the sum — of all of it. Its two children cover the left and right halves and store their sums; their children the quarters; and so on down to the leaves, which are the individual elements. Every node stores the aggregate of a contiguous range, and a parent's value is just the combination of its two children's.

Now a range query. To sum positions [i, j], start at the root and consider its range. If the node's range is entirely outside [i, j], it contributes nothing. If it's entirely inside [i, j], you take its stored aggregate directly — you don't descend, because that whole range's sum is already computed and sitting there. Only if the node partially overlaps do you split into its two children and recurse. The magic is that any range, however it's positioned, is covered by only O(log n) of these "entirely inside" nodes — the canonical segments — so the query assembles its answer from a logarithmic number of precomputed pieces. Updates are the mirror: change a leaf, then walk back up recomputing each ancestor's aggregate from its children, touching only the O(log n) nodes on that one path. Neither operation ever touches more than a logarithmic slice of the tree.

Complexity: how it scales

Building the tree is $O(n)$ — each of the ~2n nodes is computed once. A range query is $O(\log n)$: at each level of the tree the query touches at most a constant number of nodes (the canonical decomposition adds at most two per level), so the total is proportional to the height. A point update is $O(\log n)$ too — one root-to-leaf path recomputed. Space is $O(n)$. The chart runs a workload of 5000 operations split evenly between range queries and updates, against the two array approaches:

At 40000 elements the segment tree ran the mixed workload in about 25 ms, against the raw array's 152 ms (6× slower, because half its operations were O(n) range queries) and the prefix-sum array's 2544 ms (100× slower, because half its operations were O(n) rebuilds). Each array approach is fast at one operation and catastrophic at the other; the segment tree is O(log n) at both, so it wins the moment the workload mixes them — which real workloads do.

What it's good at, what it isn't

The segment tree is the right structure when you need range aggregates over data that changes — many queries and many updates, interleaved. It handles any associative operation (sum, min, max, gcd, and more) with the same code, and with the lazy-propagation extension it can even apply updates to a whole range in O(log n), not just a single point. That flexibility makes it the go-to for range problems in competitive programming and a solid choice for analytics over mutable time series or arrays.

Its costs are complexity and weight. It's more code and more memory (roughly 2n–4n nodes) than the alternatives, so if your data is static — no updates — prefix sums give O(1) queries and you should just use those. And if you only ever need prefix sums (not min or max), the Fenwick tree in the next chapter does the same job in a fraction of the code and memory. The segment tree earns its overhead when you genuinely need both mutable data and range queries of an operation beyond sums; for the narrower cases, lighter tools win.

The data, or the inputs

The face-off runs a 50/50 mix of range queries and point updates, the workload where the array approaches each hit their slow operation half the time and the segment tree's uniform O(log n) shines. The animation builds a segment tree over eight elements and traces one range query, so you can watch it decompose the range into its canonical segments.

Build it, one function at a time

The query is the heart of it — the three-way decision (outside, inside, partial) that assembles the answer from canonical segments:

def query(self, ql, qr, probe=None):
    """Sum of data[ql..qr] in O(log n). At each node: if its range is entirely
    OUTSIDE the query, it contributes 0; if entirely INSIDE, it contributes its
    stored aggregate directly — no need to descend; if it PARTIALLY overlaps, split
    into its two children. Only O(log n) nodes ever land 'entirely inside', and their
    ranges are the canonical pieces the answer is assembled from."""
    return self._query(1, 0, self._n - 1, ql, qr, probe)

def _query(self, node, lo, hi, ql, qr, probe):
    if qr < lo or hi < ql:                       # entirely outside
        return 0
    if ql <= lo and hi <= qr:                    # entirely inside → use stored sum
        if probe is not None:
            probe.append({"node": node, "lo": lo, "hi": hi, "kind": "pick"})
        return self._tree[node]
    if probe is not None:                        # partial overlap → descend
        probe.append({"node": node, "lo": lo, "hi": hi, "kind": "split"})
    mid = (lo + hi) // 2
    return (self._query(2 * node, lo, mid, ql, qr, probe)
            + self._query(2 * node + 1, mid + 1, hi, ql, qr, probe))

And the update repairs the tree by recomputing ancestors up one path:

def update(self, i, value):
    """Set data[i] = value in O(log n): change the leaf, then recompute the stored
    aggregate of every ancestor on the path back to the root — there are only log n
    of them, so no full rebuild."""
    self._update(1, 0, self._n - 1, i, value)

def _update(self, node, lo, hi, i, value):
    if lo == hi:
        self._tree[node] = value
        self._data[i] = value
        return
    mid = (lo + hi) // 2
    if i <= mid:
        self._update(2 * node, lo, mid, i, value)
    else:
        self._update(2 * node + 1, mid + 1, hi, i, value)
    self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]

Watch it work

Here's a segment tree over eight elements, and a query for the sum of range [2:6]. Each node is labelled with the range it covers. Step through the query: it starts at the root (covering 0:7, which partially overlaps, so it splits — orange), and descends. Where a node's range falls entirely inside [2:6], the query takes its stored sum without descending further (green — a canonical segment); where a node is partly in and partly out, it splits again. Watch how few green nodes it takes to cover the whole range — just three canonical segments assemble the answer of 21, instead of visiting all five elements. That handful of precomputed pieces is the O(log n):

The complete code

Both versions in one place — flip between them. The from-scratch tab is the segment tree. The library tab is the two array baselines it beats — the raw array (fast update, slow query) and prefix sums (fast query, slow update) — because there's no segment tree in the standard library; it's a structure you build for the job.

"""The segment tree — a tree over the positions of an array that answers RANGE queries
("sum, min, or max of everything between i and j") and POINT updates ("set element i")
both in O(log n).

A plain array forces a choice: keep the raw values and range queries cost O(n); keep
prefix sums and queries are O(1) but any update costs O(n) to rebuild. The segment tree
refuses the choice. Each node stores the aggregate of a contiguous range — the root the
whole array, its children the two halves, and so on down to single elements — so a query
assembles its answer from O(log n) precomputed pieces, and an update touches only the
O(log n) nodes on one root-to-leaf path.
"""


class SegmentTree:
    def __init__(self, data):
        self._n = len(data)
        self._data = list(data)
        self._tree = [0] * (4 * max(1, self._n))     # safe upper bound on node count
        if self._n:
            self._build(1, 0, self._n - 1)

    def _build(self, node, lo, hi):
        if lo == hi:
            self._tree[node] = self._data[lo]
            return
        mid = (lo + hi) // 2
        self._build(2 * node, lo, mid)
        self._build(2 * node + 1, mid + 1, hi)
        self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]

    # region: query
    def query(self, ql, qr, probe=None):
        """Sum of data[ql..qr] in O(log n). At each node: if its range is entirely
        OUTSIDE the query, it contributes 0; if entirely INSIDE, it contributes its
        stored aggregate directly — no need to descend; if it PARTIALLY overlaps, split
        into its two children. Only O(log n) nodes ever land 'entirely inside', and their
        ranges are the canonical pieces the answer is assembled from."""
        return self._query(1, 0, self._n - 1, ql, qr, probe)

    def _query(self, node, lo, hi, ql, qr, probe):
        if qr < lo or hi < ql:                       # entirely outside
            return 0
        if ql <= lo and hi <= qr:                    # entirely inside → use stored sum
            if probe is not None:
                probe.append({"node": node, "lo": lo, "hi": hi, "kind": "pick"})
            return self._tree[node]
        if probe is not None:                        # partial overlap → descend
            probe.append({"node": node, "lo": lo, "hi": hi, "kind": "split"})
        mid = (lo + hi) // 2
        return (self._query(2 * node, lo, mid, ql, qr, probe)
                + self._query(2 * node + 1, mid + 1, hi, ql, qr, probe))
    # endregion

    # region: update
    def update(self, i, value):
        """Set data[i] = value in O(log n): change the leaf, then recompute the stored
        aggregate of every ancestor on the path back to the root — there are only log n
        of them, so no full rebuild."""
        self._update(1, 0, self._n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self._tree[node] = value
            self._data[i] = value
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2 * node, lo, mid, i, value)
        else:
            self._update(2 * node + 1, mid + 1, hi, i, value)
        self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]
    # endregion

"""There's no segment tree in the standard library — it's a build-it-yourself structure.
The instructive counterparts are the two array approaches it improves on, each fast at one
operation and slow at the other:

  - a RAW array: O(1) update, but O(n) range query (you sum the slice every time);
  - a PREFIX-SUM array: O(1) range query, but O(n) update (any change rebuilds the sums).

The segment tree's pitch is O(log n) for BOTH, so it wins on any workload that mixes
queries and updates. The face-off shows exactly that.
"""


# region: naive_array
class NaiveArray:
    """Raw values: updating is trivial, but every range query re-sums the slice — O(n)."""

    def __init__(self, data):
        self._d = list(data)

    def query(self, lo, hi):
        return sum(self._d[lo:hi + 1])          # O(n)

    def update(self, i, value):
        self._d[i] = value                      # O(1)
# endregion


# region: prefix_sums
class PrefixSums:
    """Precomputed prefix sums: a range query is one subtraction — O(1) — but any update
    invalidates the sums and forces an O(n) rebuild."""

    def __init__(self, data):
        self._d = list(data)
        self._rebuild()

    def _rebuild(self):
        self._p = [0]
        for x in self._d:
            self._p.append(self._p[-1] + x)

    def query(self, lo, hi):
        return self._p[hi + 1] - self._p[lo]    # O(1)

    def update(self, i, value):
        self._d[i] = value
        self._rebuild()                         # O(n)
# endregion

Scratch vs library

This face-off is the clearest illustration in the tier of matching a structure to a workload rather than a single operation. On queries alone, prefix sums would crush the segment tree; on updates alone, the raw array would. But mix the two — as any real application does — and each array approach is dragged down by whichever operation it made O(n), while the segment tree, O(log n) at both, sails past: 6× faster than the raw array, 100× faster than prefix sums, on the same 5000-operation mix. The lesson generalizes far beyond segment trees: when you benchmark, benchmark the workload, because a structure that's optimal for one operation in isolation can be pessimal for the mixture you'll actually run. The segment tree wins not by being fastest at anything, but by having no slow operation.

Where you'll actually meet it

Segment trees run range-aggregate queries over changing data. Analytics and monitoring systems use them (and their variants) for rolling range statistics over mutable time series. Databases use interval and range trees — close relatives — to answer "which rows fall in this range" and to index geometric data. Competitive programming leans on them for an entire genre of "range query with updates" problems. Computational geometry, their birthplace, uses them for windowing and stabbing queries. And any system that must answer "the max/sum/min over this sliding or arbitrary window, while the underlying data updates" is a candidate. Whenever ranges and updates coexist, the segment tree is the general answer.

Takeaways

A segment tree stores the aggregate of every contiguous range in a binary tree, so a range query assembles its answer from $O(\log n)$ canonical segments and a point update repairs $O(\log n)$ ancestors — making both fast where a flat array must sacrifice one. It works for any associative operation, extends via lazy propagation to range updates, and is the right tool whenever mutable data meets range queries, at the cost of more code and memory than simpler structures.

The next chapter is that simpler structure, for the common special case. If your aggregate is a sum (or anything invertible) and you need prefix queries with point updates, the Fenwick tree — also called a binary indexed tree — does the same O(log n) job in a handful of lines and a single array, using a beautiful trick with the binary representation of the indices. It's the segment tree's lean, specialized sibling.