Lesson 4 · Advanced structures and algorithms

Segment Trees

Segment Trees are powerful structures that break an array into intervals, allowing both range queries and point updates in O(log N) time.

When Prefix Sums Stop Working

A prefix sum array answers any range sum in O(1) after O(n) preprocessing, which is unbeatable — as long as the underlying data never changes. A single update to element k invalidates every prefix from k onward, costing O(n) to repair.

So the difficulty is not range queries alone, nor updates alone, but both together. A plain array gives O(1) updates and O(n) queries; a prefix array gives O(n) updates and O(1) queries. With q operations mixing both, either choice degrades to O(n·q).

A segment tree balances them at O(log n) each. For a million elements and a million mixed operations, that is roughly 20 million steps rather than a trillion.

The structure is a binary tree in which every node represents an interval of the array and stores an aggregate over it. The root covers the whole array [0, n−1]; each internal node splits its interval at the midpoint and gives the halves to its two children; leaves cover single elements.

The aggregate can be any associative operation — sum, minimum, maximum, gcd, bitwise or — because a node's value is computed by combining its two children, and associativity is what makes the grouping irrelevant. This generality is the segment tree's main advantage over the Fenwick tree, which is essentially restricted to invertible operations like sum.

Note especially that minimum and maximum work here but cannot be done with prefix sums at all: there is no way to remove an element from a running minimum, so prefix-based range minimum is impossible. A segment tree has no such problem because it never subtracts — it only combines.

Prefix sums are O(1) to query but O(n) to update
Segment trees make both O(log n)
Each node holds an aggregate over the interval it covers
Any associative operation works, including min and max

Building the Tree

Construction is a recursive post-order pass. A node covering [lo, hi] where lo == hi is a leaf and stores arr[lo] directly. Otherwise it splits at mid = lo + (hi − lo) / 2, builds both children, and sets its own value to the combination of theirs.

Because each element is placed once and each internal node does O(1) work, the build is O(n) — not O(n log n), which is a common misstatement. There are fewer than 2n nodes in total, and each is computed once.

Storage is normally a flat array with no pointers, using the same index scheme as a heap: the node at index i has children at 2i + 1 and 2i + 2, or at 2i and 2i+1 under 1-based indexing. This avoids per-node allocation and keeps the structure contiguous and cache-friendly.

The array must be sized 4n, and this catches people out. The tree has fewer than 2n nodes, but when n is not a power of two the recursive splitting leaves gaps in the index space, and the deepest index can exceed 2n. 4n is the safe bound that always suffices; allocating 2n produces out-of-bounds writes on non-power-of-two inputs, which is a genuinely common bug.

An alternative is to pad the array up to the next power of two with identity elements — 0 for sum, +∞ for minimum — which makes the tree perfect and allows an iterative bottom-up implementation that is shorter and faster than the recursive one.

Recursive build: leaves take elements, parents combine children
O(n) to build, not O(n log n)
Stored flat like a heap — children of i at 2i+1 and 2i+2
Allocate 4n, not 2n — index gaps appear when n is not a power of two

Queries and Point Updates

A range query over [l, r] recurses from the root, and each node it reaches falls into one of three cases. This three-way split is the algorithm, and stating it clearly is most of a good exam answer.

No overlap — the node's interval lies entirely outside [l, r]. Return the identity for the operation: 0 for sum, +∞ for minimum, −∞ for maximum. Returning the wrong identity is a frequent bug, and it silently corrupts results rather than crashing.

Total overlap — the node's interval lies entirely inside [l, r]. Return the node's stored value without descending further. This is where the efficiency comes from: an entire subtree is answered by one lookup.

Partial overlap — recurse into both children and combine their results.

The complexity argument is worth knowing. At each level of the tree, at most two nodes are partially overlapped — one at each end of the query range — and every other node is either fully inside or fully outside, terminating immediately. With O(log n) levels and O(1) partial nodes per level, a query visits O(log n) nodes. Equivalently, any range decomposes into at most O(log n) canonical fully-covered intervals.

A point update sets arr[i] to a new value. Descend to the leaf covering i, update it, then recompute every ancestor on the way back up by recombining its children. The path from root to leaf has length O(log n), so the update is O(log n) — and only that single path changes, since no other node's interval contains i.

Segment tree costs against the alternatives
	Plain array	Prefix sums	Segment tree
Build	—	O(n)	O(n)
Range query	O(n)	O(1)	O(log n)
Point update	O(1)	O(n)	O(log n)
Range update	O(n)	O(n)	O(log n) with lazy
Min / max queries	O(n)	Impossible	O(log n)
Space	O(n)	O(n)	O(4n)

Three cases: no overlap returns identity, total overlap returns the value
Partial overlap recurses both ways and combines
At most two partial nodes per level, so a query is O(log n)
A point update rewrites one root-to-leaf path

Key reference

Terms, operations, and practical uses

Tree Anatomy

Interval RepresentationEach node represents an aggregate value (sum, min, max) over a contiguous subarray segment.
Root IntervalThe root node always represents the aggregate of the entire array from index 0 to N-1.
Leaf NodesThe leaves of the tree represent intervals of length 1 (the individual array elements).

Core Operations

Tree ConstructionBuilt recursively in O(N) time by assigning each node the combination of its two children.
Range QueryRetrieving the aggregate of an arbitrary interval in O(log N) time by combining completely overlapped nodes.
Point UpdateModifying a single array element and recursively updating its O(log N) ancestors up to the root.

Advanced Techniques

Lazy PropagationAn optimization for Range Updates. Instead of updating all descendants, a 'lazy' tag is stored and pushed down only when queried.
Memory LayoutTypically stored in a flat array of size 4N, using 2*i and 2*i + 1 for child traversal.
Dynamic Segment TreesNodes are created via pointers only when needed, vastly saving memory when the array size N is extremely large (e.g., 10^9).

Implementation

Query a range-sum segment tree

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 1, 0, self.n - 1)
    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            self.build(data, 2 * node, start, mid)
            self.build(data, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return self.query(2*node, start, mid, l, r) + self.query(2*node+1, mid+1, end, l, r)

tree = SegmentTree([1, 3, 5, 7])
print('sum(1..2) =', tree.query(1, 0, 3, 1, 2))

#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
    vector<int> tree;
    int n;
    void build(vector<int>& arr, int v, int tl, int tr) {
        if(tl == tr) {
            tree[v] = arr[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(arr, v*2, tl, tm);
            build(arr, v*2+1, tm+1, tr);
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    public:
    SegmentTree(vector<int> arr) : tree(4 * arr.size()), n(arr.size()) {
        build(arr, 1, 0, n - 1);
    }
    int query(int v, int tl, int tr, int l, int r) {
        if (r < tl || tr < l) return 0;
        if (l <= tl && tr <= r) return tree[v];
        int tm = (tl + tr) / 2;
        return query(v*2, tl, tm, l, r) + query(v*2+1, tm+1, tr, l, r);
    }
    int size() const {
        return n;
    }
};
int main() {
    SegmentTree tree({1, 3, 5, 7});
    cout << "sum(1..2) = " << tree.query(1, 0, tree.size() - 1, 1, 2) << '\n';
}

public class Main {
    static class SegmentTree {
        int[] tree;
        int n;
        SegmentTree(int[] arr) {
            n = arr.length;
            tree = new int[4 * n];
            build(arr, 1, 0, n - 1);
        }
        void build(int[] arr, int v, int tl, int tr) {
            if(tl == tr) {
                tree[v] = arr[tl];
            } else {
                int tm = (tl + tr) / 2;
                build(arr, v*2, tl, tm);
                build(arr, v*2+1, tm+1, tr);
                tree[v] = tree[v*2] + tree[v*2+1];
            }
        }
        int query(int v, int tl, int tr, int l, int r) {
            if (r < tl || tr < l) return 0;
            if (l <= tl && tr <= r) return tree[v];
            int tm = (tl + tr) / 2;
            return query(v*2, tl, tm, l, r) + query(v*2+1, tm+1, tr, l, r);
        }
    }
    public static void main(String[] args) {
        SegmentTree tree = new SegmentTree(new int[]{1, 3, 5, 7});
        System.out.println("sum(1..2) = " + tree.query(1, 0, tree.n - 1, 1, 2));
    }
}

Watch it run

Step through it

Running on array = [1, 3, 5, 7], sum indices 1..2

Output

Read all 13 Steps

The array Array [1, 3, 5, 7]. The four leaves of the tree are exactly these elements.
Pair the leaves The parent of leaves 1 and 3 stores their sum, 4, covering array range [0..1].
Pair the others The other internal node stores 5 + 7 = 12 for range [2..3].
Build the root The root sums its two children: 4 + 12 = 16, covering the whole array [0..3]. Building costs O(n).
Query sum(1..2) Ask for the sum of indices 1 through 2. Start at the root and compare ranges.
Root partially overlaps The root covers [0..3], which only partly overlaps [1..2]. Partial overlap means recurse into both children.
Left child partial Node [0..1] partly overlaps [1..2] as well, so recurse again rather than using its stored 4.
Leaf outside Leaf [0..0] holding 1 lies entirely outside the query. Return the identity value 0 and stop.
Leaf inside Leaf [1..1] holding 3 is fully inside the query. Return 3 immediately.
Full cover Node [2..3] would overshoot, so recurse; leaf [2..2] holding 5 is fully inside and returns 5.
Combine The returned pieces add up: 3 + 5 = 8. Only a handful of nodes were touched, never the whole array.
Point update Now set index 1 from 3 to 10. Only the leaf and its ancestors change.
Repair upward The leaf's parent becomes 1 + 10 = 11, and the root becomes 11 + 12 = 23. One path, O(log n) work.

Lazy Propagation

Point updates are O(log n), but a range update — 'add 5 to every element between l and r' — would naively touch every leaf in the range, costing O(n) and discarding the structure's advantage.

Lazy propagation fixes this by refusing to do work until it is needed. Each node gains a pending field recording an update that applies to its entire interval but has not yet been pushed to its children.

When a range update fully covers a node's interval, apply the change to that node's own aggregate and record the pending value on it — then stop, without descending. The children are now stale, but nothing has read them yet, so it does not matter.

The obligation this creates is that every subsequent traversal through that node must push the pending value down first: apply it to both children, record it as pending on each of them, and clear it on the parent. This push happens at the top of both the query and the update routines, before any recursion, and forgetting it is the single defining bug of lazy propagation.

With the push in place, a range update visits the same O(log n) nodes a range query does, and range updates become O(log n) rather than O(n).

One detail requires care. Applying a pending update to a node's aggregate is not simply adding the value — for a sum, adding v to every element of an interval of length len increases the aggregate by v · len, so the interval length must be known or derivable. For a minimum or maximum, the same update adds v directly. The composition rule for combining two pending updates also depends on the operation: additions compose by adding, but assignments overwrite, and mixing the two requires representing pending updates as a pair.

Segment trees extend in several directions worth knowing by name: a merge sort tree stores a sorted list at each node to answer 'how many values in this range are below x'; a persistent segment tree keeps every historical version by sharing unchanged subtrees; and a 2-D segment tree answers rectangle queries on a grid at O(log² n).

Store a pending update at a node instead of descending to its children
Push it down at the start of every query and update that passes through
Forgetting the push is the defining lazy-propagation bug
For sums the pending value scales by the interval length