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.

Beyond Prefix Sums

While Prefix Sums are perfect for static arrays, they fail when array values change, requiring O(N) time to rebuild the sums. A Segment Tree solves this by storing aggregated information (like sums, minimums, or maximums) for hierarchical intervals of the array.

Tree Construction

The root of a segment tree represents the entire array. Its two children represent the left and right halves. This halving continues recursively until the leaves, which represent individual array elements. Building the tree takes O(N) time and requires an array size of 4N.

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 2i and 2i + 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).

Code example

Build 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]
tree = SegmentTree([1, 3, 5, 7])
print('Tree built')

class SegmentTree {
    vector<int> tree;
    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];
        }
    }
};

class SegmentTree {
    int[] tree;
    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];
        }
    }
}

Inputarray = [1, 3, 5, 7]

OutputTree built

Example

Run the example step by step

Output

Range Queries

To query an interval, we start at the root and recursively traverse down. If a node's interval is completely contained within our query range, we return its precomputed value immediately. If it partially overlaps, we split the query to its children. This takes O(log N) time.

Logarithmic Updates

When a single array element is updated, we only need to update the segment tree leaves and its direct ancestors up to the root. Since the tree height is bounded by log(N), updating an element and recalculating the affected intervals takes O(log N) time.