01 — Segment Trees¶

Phase 5 | Weeks 30–32 | Feb 23 – Mar 8, 2027

A segment tree is a binary tree built on an array that answers range queries and handles point updates in O(log n) each. Without it, range queries are O(n) per query; with a prefix sum array you can answer range sum queries in O(1) but updates are O(n). Segment trees give you both: O(log n) query AND O(log n) update. That tradeoff is why they exist. This file goes from the intuition to full implementation to lazy propagation.

The Problem They Solve¶

Given: An array arr of n elements. Queries: “What is the sum (or min/max) of elements in range [l, r]?” Updates: “Set arr[i] = x” or “Add x to all elements in [l, r].”

Approach	Query	Update	Build
Naive	O(n)	O(1)	O(n)
Prefix Sum	O(1)	O(n)	O(n)
Segment Tree	O(log n)	O(log n)	O(n)
Segment Tree + Lazy	O(log n)	O(log n) range	O(n)

When queries and updates are interleaved, segment tree wins. When there are no updates, prefix sum is sufficient.

Tree Structure¶

Array representation: Store the segment tree in a 1-indexed array tree of size 4n. Node at index i:

Left child: 2i
Right child: 2i + 1
Parent: i // 2

Node semantics: tree[i] stores the aggregate (sum/min/max) of some contiguous segment of the original array. The root (tree[1]) covers the entire array [0, n-1]. Each node covers the union of its two children.

Original: [2, 1, 3, 4, 5]

Tree structure (sum):
           tree[1]=15 [0..4]
          /               \
   tree[2]=6 [0..2]    tree[3]=9 [3..4]
    /         \            /       \
tree[4]=3   tree[5]=3  tree[6]=4  tree[7]=5
  [0..1]      [2..2]    [3..3]     [4..4]
  /    \
tree[8]=2  tree[9]=1
  [0..0]    [1..1]

Build: O(n)¶

def build(node, start, end, arr, tree):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build(2*node, start, mid, arr, tree)
        build(2*node+1, mid+1, end, arr, tree)
        tree[node] = tree[2*node] + tree[2*node+1]  # or min/max

Call: build(1, 0, n-1, arr, tree)

Point Update: O(log n)¶

Update arr[idx] = val. Walk down from root to the leaf, updating aggregates on the way back up.

def update(node, start, end, idx, val, tree):
    if start == end:
        tree[node] = val      # leaf: set new value
    else:
        mid = (start + end) // 2
        if idx <= mid:
            update(2*node, start, mid, idx, val, tree)
        else:
            update(2*node+1, mid+1, end, idx, val, tree)
        tree[node] = tree[2*node] + tree[2*node+1]  # recompute from children

Range Query: O(log n)¶

Query sum of arr[l..r]. Three cases at each node:

Full overlap: Current node’s segment is completely inside [l, r] → return tree[node]
No overlap: Current node’s segment is completely outside [l, r] → return 0 (or identity element)
Partial overlap: Query both children and combine

def query(node, start, end, l, r, tree):
    if r < start or end < l:
        return 0                   # no overlap
    if l <= start and end <= r:
        return tree[node]          # full overlap
    mid = (start + end) // 2
    left  = query(2*node, start, mid, l, r, tree)
    right = query(2*node+1, mid+1, end, l, r, tree)
    return left + right            # partial overlap: combine

Lazy Propagation: Range Updates in O(log n)¶

The problem: “Add 5 to every element in [l, r].” Without lazy propagation, you’d update every element individually — O(n) in the worst case.

The idea: When you need to update an entire segment [l, r], mark the nodes covering [l, r] as “pending” using a lazy array. Don’t propagate the update to children yet. Only when you need to query or update a child do you “push down” the pending lazy value.

Lazy array: lazy[node] = pending update that applies to all elements in this node’s segment but hasn’t been pushed to children yet.

Push Down¶

Before accessing a node’s children, propagate any pending lazy value:

def push_down(node, start, end, tree, lazy):
    if lazy[node] != 0:
        mid = (start + end) // 2
        # Apply pending update to children
        tree[2*node]   += lazy[node] * (mid - start + 1)
        tree[2*node+1] += lazy[node] * (end - mid)
        lazy[2*node]   += lazy[node]
        lazy[2*node+1] += lazy[node]
        lazy[node] = 0   # clear this node's lazy value

The * (segment_length) factor is because tree[node] stores the sum of the segment, and adding val to each element adds val * length to the sum.

Range Update with Lazy¶

def update_range(node, start, end, l, r, val, tree, lazy):
    if r < start or end < l:
        return                     # no overlap
    if l <= start and end <= r:
        # Full overlap: update this node's sum, mark lazy for children
        tree[node] += val * (end - start + 1)
        lazy[node] += val
        return
    push_down(node, start, end, tree, lazy)  # push before going deeper
    mid = (start + end) // 2
    update_range(2*node, start, mid, l, r, val, tree, lazy)
    update_range(2*node+1, mid+1, end, l, r, val, tree, lazy)
    tree[node] = tree[2*node] + tree[2*node+1]

Range Query with Lazy¶

def query_lazy(node, start, end, l, r, tree, lazy):
    if r < start or end < l:
        return 0
    if l <= start and end <= r:
        return tree[node]
    push_down(node, start, end, tree, lazy)  # push before going deeper
    mid = (start + end) // 2
    left  = query_lazy(2*node, start, mid, l, r, tree, lazy)
    right = query_lazy(2*node+1, mid+1, end, l, r, tree, lazy)
    return left + right

The only difference from the non-lazy query: the push_down call before recursing. That single call is what makes the whole system work.

Segment Tree Variants¶

Range Minimum Query (RMQ): Replace sum with min. Identity element is ∞. Push-down formula omits the length factor (min doesn’t accumulate).

Range Maximum Query: Same as RMQ with max. Identity element is -∞.

Count elements in range: tree[node] = count of active elements. Update = set to 0 or 1. Used in order statistic queries.

Coordinate compression: When values are large (up to 10^9) but count is small (n ≤ 10^5), compress values to [0, n-1] before building the tree.

Applications¶

Range Sum Query + Point Update — LeetCode 307 (the baseline problem)
Count Inversions in Array — Segment tree on values; for each element, query how many previous elements are greater
Merge Intervals with Updates — Tracking active intervals
Rectangle Area Union — 2D segment tree or sweep line + 1D segment tree
Sliding Window Maximum — Often solved with monotonic deque, but segment tree also works

What Most Engineers Get Wrong¶

Lazy push-down timing. You MUST push down before visiting a node’s children — both in updates and queries. Forgetting this means children still have stale values, producing correct-looking code that fails on interleaved range update + range query sequences. The bug is silent until you test a case where a query follows a range update on an overlapping range.

Array size. The segment tree array needs size 4n, not 2n or n. The reason: the tree height is ceil(log2(n)), and with 1-indexed storage, the last level can have up to 2 * 2^ceil(log2(n)) nodes. For n that’s not a power of 2, this can exceed 2n. Use 4n to be safe.

Identity elements for different aggregates. Sum: 0. Min: +∞. Max: -∞. XOR: 0. Product: 1. Using the wrong identity causes incorrect results on empty-range queries.

Practice Problems¶

Medium¶

Range Sum Query - Mutable — LeetCode 307. The baseline segment tree problem. Point update + range query.
Count of Smaller Numbers After Self — LeetCode 315. Segment tree with coordinate compression, or merge sort. The hardest medium here.

Hard¶

My Calendar III — LeetCode 732. Range update (add 1 to [start, end]) + point query (find max). Lazy propagation practice.
Rectangle Area II — LeetCode 850. Sweep line + segment tree. Requires coordinate compression.
Falling Squares — LeetCode 699. Range max query + range update. Lazy propagation on max instead of sum.