Segment TreeSegment trees

01Why it exists

Reach for it when you see:Range sums or range maxima, needing queries and updates at the same time, O(n) being too slow, associative operations, sweep lines.

02The core idea

Every node of a segment tree owns a contiguous range of indices and stores that range's aggregate. The root owns [0, n−1], hands half to each child, and the splitting continues until a leaf owns a single element. That makes a tree of height log n, usually stored in a flat array where the children of node i are 2i and 2i+1; allocating 4n slots is always enough.

Querying [l, r] starts at the root, and each node compares its own range with [l, r]. If they are completely disjoint, it returns the empty value (0 for a sum, −∞ for a maximum). If the node is fully contained, it returns its stored value outright and the whole subtree below is never entered. Only on partial overlap does it split the work between its two children. At most two nodes per level can be partially overlapping, so a query touches O(log n) nodes in total.

Point updates are simpler still: walk from the root down to the leaf, change the leaf's value, and on the way back recompute each ancestor from its children. One path, O(log n). Building the tree is a single post-order traversal, O(n).

Any operation that is associative can be swapped in: sum, maximum, minimum, GCD, XOR, even matrix multiplication. When you need range updates (add v to all of [l, r]), reach for lazy propagation: record "everything below gets +v" on the nodes that exactly cover the range, and only push that mark down when you actually descend. This is the most common advanced version of a segment tree, and it is also where it parts ways with the Fenwick tree in the next lesson: a Fenwick tree is lighter and quicker to write, but it is only good at prefix sums and point updates.

03The algorithm

1. 1Decide what each node stores (sum, maximum, …) and what the empty range is worth (0, −∞, …). Allocate tree = [0] * (4n).
2. 2build(node, lo, hi): if lo == hi, store a[lo]; otherwise split in half, recurse, and finish with tree[node] = merge(left, right).
3. 3query(node, lo, hi, ql, qh): return the empty value when the ranges are disjoint; return tree[node] when the node is fully contained; otherwise merge the results from both children.
4. 4update(node, lo, hi, i, v): walk down to the leaf, change it, and recompute each ancestor on the way back up.
5. 5For range updates, add lazy propagation: give each node a lazy field and push the pending mark down before descending into a child.

04Interactive demo

Range sums over eight elements. During the query for [2, 5], watch which nodes get taken as they are (green), which are skipped (grey), and which have to split further. Then add 4 to index 3 and watch the ancestors along a single path get refreshed.

05Code

A complete implementation of range sum with point updates, storing the nodes in a 1-indexed heap-style array. The last line is a reminder that switching to a maximum means changing three places.

class SegmentTree:
    """Range sum with point updates. The children of tree[i] are 2i and 2i+1 (1-indexed heap layout)"""

    def __init__(self, a):
        self.n = len(a)
        self.tree = [0] * (4 * self.n)       # 4n is always enough
        self._build(1, 0, self.n - 1, a)

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

    def query(self, ql, qh):
        return self._query(1, 0, self.n - 1, ql, qh)

    def _query(self, node, lo, hi, ql, qh):
        if qh < lo or hi < ql:                # no overlap at all
            return 0
        if ql <= lo and hi <= qh:             # fully contained: use it as is
            return self.tree[node]
        mid = (lo + hi) // 2                  # partial overlap: split and recurse
        return (self._query(2 * node, lo, mid, ql, qh) +
                self._query(2 * node + 1, mid + 1, hi, ql, qh))

    def update(self, i, value):
        self._update(1, 0, self.n - 1, i, value)

    def _update(self, node, lo, hi, i, value):
        if lo == hi:
            self.tree[node] = 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]   # refresh the ancestors on the way back up


st = SegmentTree([5, 3, 8, 6, 2, 7, 4, 1])
print(st.query(2, 5))     # 8 + 6 + 2 + 7 = 23
st.update(3, 10)
print(st.query(2, 5))     # 27

# For a range maximum instead: change the three "+" to max and return -inf when the ranges are disjoint

06Practice

• LeetCode 307Range Sum Query - MutableMedium
• LeetCode 315Count of Smaller Numbers After SelfHard
• LeetCode 2407Longest Increasing Subsequence II (range maximum)Hard
• LeetCode 218The Skyline Problem (a sweep-line way of thinking)Hard
• LeetCode 850Rectangle Area II (sweep line plus range cover)Hard