Segment Tree (Range Query + Update)

Segment Tree: Range Queries and Point Updates

A prefix-sum array answers range-sum queries in $O(1)$, but it breaks down the moment the underlying data changes. Recomputing the entire prefix array after a single update costs $O(n)$, which is unacceptable when queries and updates are interleaved. The segment tree solves exactly this problem: it answers arbitrary range queries (sum, minimum, maximum, GCD, or any associative operation) and handles point updates, both in $O(\log n)$.

The Tree Structure

A segment tree is a complete binary tree built over an array of length n. Each node stores the aggregate answer for a contiguous subrange of the array. The root covers [0, n-1]. Its left child covers [0, mid] and its right child covers [mid+1, n-1], where mid = (0 + n-1) // 2. This splitting continues recursively until every leaf corresponds to a single element.

In practice the tree is stored as a flat array of size 4n. If a node sits at index node, its left child is at 2*node and its right child is at 2*node+1. This 1-indexed convention means the root lives at index 1, and the math stays branchless.

Building the Tree

Construction is a simple post-order recursion: fill the leaves first, then combine children to populate each internal node.

class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)

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

After build, self.tree[1] holds the sum of the entire array.

Querying a Range

To answer a range-sum query [l, r], the tree is traversed top-down. At each node covering [lo, hi], there are three cases:

• The node's range is entirely outside [l, r]: return 0 (the identity for sum).
• The node's range is entirely inside [l, r]: return tree[node] immediately.
• The ranges partially overlap: recurse into both children and add their results.

The key insight is that any query range [l, r] can be covered by $O(\log n)$ non-overlapping nodes, so the recursion terminates quickly.

    def query(self, node, lo, hi, l, r):
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.tree[node]
        mid = (lo + hi) // 2
        left  = self.query(2 * node,     lo,      mid, l, r)
        right = self.query(2 * node + 1, mid + 1, hi,  l, r)
        return left + right

Callers invoke this as st.query(1, 0, st.n - 1, l, r).

Updating a Single Element

A point update changes arr[idx] to val. The tree update mirrors a binary search: follow the path from the root to the target leaf, then recompute each internal node on the way back up.

    def update(self, node, lo, hi, idx, val):
        if lo == hi:
            self.tree[node] = val
            return
        mid = (lo + hi) // 2
        if idx <= mid:
            self.update(2 * node,     lo,      mid, idx, val)
        else:
            self.update(2 * node + 1, mid + 1, hi,  idx, val)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Only the $O(\log n)$ nodes on the root-to-leaf path are touched; everything else remains valid.

Walked Example

Array: [3, 1, 4, 1, 5]. After build, the root holds 14 (total sum). Querying [1, 3] returns 1+4+1 = 6. The traversal splits at the root, finds that [0, 2] partially overlaps [1, 3] and [3, 4] partially overlaps [1, 3], then resolves both sub-problems with further splits until it lands on the leaves at indices 1, 2, and 3. Now update index 2 to 10: the path root -> left child -> right grandchild -> leaf is updated, and the root becomes 20.

Lazy Propagation for Range Updates

Point updates are $O(\log n)$, but a naive range update, such as "add 5 to every element in [l, r]", would require updating each leaf individually, costing $O(n)$ in the worst case. Lazy propagation fixes this by deferring work.

Each node gains a lazy field that records a pending update not yet pushed to its children. When a range update covers a node entirely, store the delta in lazy and update tree[node] immediately (you know how many elements it covers, so you can compute the new aggregate without descending). When a future query or update needs to descend through that node, first push the lazy value down to the two children, then proceed normally.

The mental model: a node's tree value is always correct for the range it covers, but its children may not yet know about updates that have been applied through the parent. The push-down step reconciles them just in time.

class LazySegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.n - 1)

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

    def _push(self, node, lo, hi):
        if self.lazy[node]:
            mid = (lo + hi) // 2
            left, right = 2 * node, 2 * node + 1
            self.tree[left]  += self.lazy[node] * (mid - lo + 1)
            self.tree[right] += self.lazy[node] * (hi - mid)
            self.lazy[left]  += self.lazy[node]
            self.lazy[right] += self.lazy[node]
            self.lazy[node] = 0

    def range_add(self, node, lo, hi, l, r, delta):
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            self.tree[node] += delta * (hi - lo + 1)
            self.lazy[node] += delta
            return
        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        self.range_add(2 * node,     lo,      mid, l, r, delta)
        self.range_add(2 * node + 1, mid + 1, hi,  l, r, delta)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, lo, hi, l, r):
        if r < lo or hi < l:
            return 0
        if l <= lo and hi <= r:
            return self.tree[node]
        self._push(node, lo, hi)
        mid = (lo + hi) // 2
        return (self.query(2 * node,     lo,      mid, l, r)
              + self.query(2 * node + 1, mid + 1, hi,  l, r))

The two crucial details: when applying a delta to a fully-covered node, multiply by the size of its range (hi - lo + 1) because the stored value is a sum over many elements. And _push must run before descending into children during either a query or a partial-range update, otherwise the children's stored aggregates would be stale.

Applications

LeetCode 307. Range Sum Query - Mutable is the canonical segment-tree problem: range sum queries on an array that supports point updates. A Fenwick tree also works here, but segment trees scale to richer operations.

LeetCode 715. Range Module tracks half-open intervals under add, query, and remove operations, a perfect fit for a segment tree with lazy propagation over a coordinate-compressed index space.

LeetCode 218. The Skyline Problem can be solved by a segment tree that supports range-maximum queries and lazy range updates, after coordinate-compressing the x-coordinates of the buildings.

LeetCode 2407. Longest Increasing Subsequence II wants the longest increasing subsequence with adjacent differences bounded by k, solved by a segment tree over the value range that supports range-maximum queries and point updates.

Generalizing to Other Operations

Any associative operation works in place of addition. For range-minimum queries, replace the + merge with min and use float('inf') as the identity. For range-maximum, use max and float('-inf'). The structure of build, query, and update stays identical: only the merge function and identity value change.

Complexity

Building the tree takes $O(n)$ time. Each query and each point update runs in $O(\log n)$. Lazy-propagation range updates also run in $O(\log n)$. Space is $O(n)$ for the tree array (the 4n allocation handles all shapes of n safely).

Recognizing this pattern

You're probably looking at a segment tree when:

• The problem mixes range queries with mutations and the operation is not invertible (min, max, GCD, bitwise OR), so a Fenwick tree won't work.
• You need range updates and range queries in the same problem, which forces lazy propagation.
• The aggregate is associative but each node has to store more than a single number (e.g., max with count, "longest valid bracket" summary).
• The input is a static value range you've coordinate-compressed and you want to insert points and query running maxima or counts.

Common templates:

• Point update + range query (min/max/GCD): sum-style build, recursive query splits the range, no lazy needed. Example: Range Sum Query - Mutable.
• Lazy range add + range sum: push pending adds to children before recursing. Example: Range Sum Query 2D - Mutable.
• Segment tree over a value range: index by compressed value, query prefix max while sweeping inputs. Example: Longest Increasing Subsequence II.
• Interval set with lazy assign: half-open intervals tracked via lazy "set to 0/1." Example: Range Module.
• Sweep-line with segment tree of maxima: coordinate-compress x-values, lazy range-max updates. Example: The Skyline Problem.