Day 19 — Segment Trees

Here’s a deceptively hard problem: given an array, answer “what’s the sum of elements between index i and j?” — but the array keeps changing between queries. A plain prefix-sum array answers the query in O(1), but a single update forces you to rebuild O(n) of it. A plain array updates in O(1), but each query costs O(n). Either way, one operation is fast and the other is slow.

The segment tree is the structure that makes both O(log n). It’s a binary tree where every node owns a range of the array and stores an aggregate (sum, min, max, gcd, …) over that range. Query and update both walk a single root-to-leaf-ish path.

A sum segment tree over [5, 2, 8, 1, 9, 3]

each node = sum of its range [lo,hi]; leaves = the array

The root holds the total (28). Each node splits its range in half and holds the sum of that half. A query for sum(1,4) is assembled from a few internal nodes — never by scanning all the cells. An update touches only the nodes on one root-to-leaf path.

What you’ll learn today

Why prefix sums fail under updates — the exact trade-off the segment tree resolves
The structure — every node owns a range [lo, hi] and stores an aggregate; leaves are the array
build, query, update — the three-function recursive template, in O(n), O(log n), O(log n)
Lazy propagation — the trick that makes range updates (add 5 to all of [i, j]) also O(log n)
Fenwick / Binary Indexed Trees — a smaller, faster structure for the common prefix-sum case
Eight interview problems — Range Sum Query Mutable, RMQ, Count of Smaller After Self, Reverse Pairs, 2D Range Sum, My Calendar III, Falling Squares

The one-sentence pitch: a segment tree turns “aggregate over any subrange, with updates in between” from O(n) per operation into O(log n). Any operation that’s associative — sum, min, max, gcd, bitwise OR/AND, matrix product — can live in a segment tree. If a problem asks for repeated range queries on a mutable array, this is almost always the structure.

Roadmap

Introduction — the range-query-with-updates problem, why prefix sums break, and how the tree fixes it.
The Template — build, query, update with the array-based representation, full code, and an interactive tree.
Lazy Propagation — range updates in O(log n) by deferring work to the nodes you actually visit.
Fenwick Tree (BIT) — the lightweight alternative when you only need prefix sums; the i & -i magic explained.
Basic Questions — warm-ups: range sum, range min, the BIT update/query loop, coordinate compression.
Practice Questions — eight interview classics, segment tree and BIT.

This is the heavy machinery of competitive programming and the second specialized structure of Phase 6. It pairs naturally with Day 18’s tries (string ranges) and feeds directly into Day 26’s divide-and-conquer counting problems.

Up next: Day 20 — Union Find, the structure for dynamic connectivity.

Maximum XOR of Two Numbers Introduction

Finished this page?