Segment Trees

The 10-second versionCopy Anchor Link

A segment tree answers questions about ranges of an array — "what's the sum (or min, or max) from index l to r?" — while still letting you change individual elements. It does this by storing, at every node of a binary tree, the answer for one contiguous slice of the array. The root covers everything, its two children cover the left and right halves, and so on down to single elements. Any range you ask about can be stitched together from O(log n) of those stored slices, and any element you change sits on just one root-to-leaf path — so both operations cost O(log n). Keeping range queries and updates cheap at once is the whole point.

Why this existedCopy Anchor Link

Picture the early days of computational geometry. You have a pile of points or rectangles on a plane, and you keep asking questions like "how many rectangles cover this vertical line?" This is a stabbing query — a range query wearing a costume. The natural first tool was a prefix sum: precompute, for every index, the total of everything up to it, and then any range answer is one subtraction. Brilliant — until something moves.

The trouble is brutal and symmetric. Keep a raw array and a range query is O(n) (add them all up). Keep prefix sums and the query is O(1) but any single update forces you to rebuild the whole table — also O(n). You get to pick one fast operation and one slow one. Nobody wanted to pick.

• 1977 — Jon Bentley, working on the classic problem of handling rectangles and interval queries efficiently, sketches a family of range structures in his work on Klee's rectangle problems. The insight: precompute answers for hierarchically nested ranges, not just prefixes.
• late 1970s–1980s — the idea splits into named relatives: the interval tree for stabbing queries, and the segment tree for aggregate queries over ranges. They share the same skeleton — a balanced tree whose nodes own ranges.
• 1980s onward — segment trees become a workhorse of computational geometry, and later a fixture of algorithmic contests, where lazy propagation let a range update be as cheap as a range query.

Why it mattered then: geometry pipelines were drowning in repeated scans. A structure that answered "give me this slice's aggregate" in O(log n) — and survived edits — turned an O(n) inner loop into a logarithmic one. That is the difference between usable and not.

Inside the inventor's headCopy Anchor Link

Start from the obvious. You want every possible range's aggregate available instantly. So why not precompute them all? There are about n²/2 ranges — way too many to store, and rebuilding them on an update is even worse. Dead end.

So Bentley squints at the requirement. He doesn't need every range; he needs enough ranges that any range can be tiled from a few of them. And there is a natural family of ranges that nest perfectly: split the array in half, and recurse. The ranges on each level are disjoint and tile the array, and there are only O(log n) levels.

Here's the trap he has to dodge next: a naive recursive tree stores nodes → children as pointers, and you think you've saved space. But for an array of n items you need up to 2n - 1 nodes, and pointer-chasing is slow. The simpler layout wins: put the tree in a flat array of size 4n, index nodes from 1, and let node i keep its children at 2i and 2i+1. No pointers, perfect cache behavior, and the 4n guarantees room even in the unbalanced deep corner where a power-of-two estimate would overflow.

Contrast the two worlds — the trap and the fix:

// Naive: sum the requested range by hand — O(n) per queryconst rangeSum = (a, l, r) => {  let total = 0;  for (let i = l; i <= r; i++) total += a[i];  return total;};// Segment tree: the aggregate is already sitting in O(log n) nodesfunction segQuery(node, l, r, ql, qr) {  if (qr < l || r < ql) return 0;                 // disjoint  if (ql <= l && r <= qr) return tree[node];      // fully covered  const mid = (l + r) >> 1;  return segQuery(2 * node, l, mid, ql, qr)       + segQuery(2 * node + 1, mid + 1, r, ql, qr);}

The naive one re-does work you already have. The tree version refuses to recompute; it just reads precomputed slices.

The final approachCopy Anchor Link

The structure, laid outCopy Anchor Link

For n = 5, node 1 covers the whole array, and each child covers half of its parent's range. The leaves are the elements themselves:

The flat store is just these nodes in array order: index 1 at the top, children of node i at 2i and 2i+1. We size it 4 × n so even a lopsided recursion never writes out of bounds.

The algorithmCopy Anchor Link

• Build recurses to the leaves, then fills each internal node as combine(left, right).
• Query walks down only where the query range overlaps; fully-covered nodes are returned whole, disjoint nodes are thrown away, and partial nodes split.
• Update descends the single path to the target leaf, changes it, and recomputes the aggregate on the way back up.
• Range update (with lazy propagation) attaches a pending change to the O(log n) nodes that a range decomposes into, and pushes those pending values down only when a later query or update actually needs to look inside.

The invariantsCopy Anchor Link

1. Every node's value equals combine of its two children. This is what makes reading a fully-covered node equivalent to summing its whole range.
2. Ranges tile cleanly. Node i's range is the union of its children's ranges, which are the two halves; the leaves partition the original array. So any query range is exactly a union of some set of canonical node ranges.
3. With lazy propagation, a node's stored value already includes any pending tag applied to its own range, but its children may be stale — the tag waits there until someone descends past it.

A worked traceCopy Anchor Link

Take a = [2, 4, 1, 7, 3] and build:

• Leaves: node 8 = 2, node 9 = 4, node 5 = 1, node 6 = 7, node 7 = 3.
• node 4 = 2 + 4 = 6, node 2 = 6 + 1 = 7, node 3 = 7 + 3 = 10, node 1 = 7 + 10 = 17.

Now query sum of [1, 3] (expected 4 + 1 + 7 = 12):

And a point update a[2] = 10: descend node 1 → node 2 → node 5, set it to 10, then recompute node 2 = 6 + 10 = 16 and node 1 = 16 + 10 = 26. One path touched. That's the O(log n).

It in codeCopy Anchor Link

function makeSegTree(a) {  const n = a.length;  const tree = new Array(4 * n).fill(0);  const build = (node, l, r) => {    if (l === r) { tree[node] = a[l]; return; }    const mid = (l + r) >> 1;    build(2 * node, l, mid);    build(2 * node + 1, mid + 1, r);    tree[node] = tree[2 * node] + tree[2 * node + 1];  };  const update = (node, l, r, idx, value) => {    if (l === r) { tree[node] = value; return; }    const mid = (l + r) >> 1;    if (idx <= mid) update(2 * node, l, mid, idx, value);    else            update(2 * node + 1, mid + 1, r, idx, value);    tree[node] = tree[2 * node] + tree[2 * node + 1];  };  const query = (node, l, r, ql, qr) => {    if (qr < l || r < ql) return 0;                // disjoint    if (ql <= l && r <= qr) return tree[node];     // fully covered    const mid = (l + r) >> 1;    return query(2 * node, l, mid, ql, qr)         + query(2 * node + 1, mid + 1, r, ql, qr);  };  build(1, 0, n - 1);  return {    update: (i, v) => update(1, 0, n - 1, i, v),    query: (l, r) => query(1, 0, n - 1, l, r),  };}

ComplexityCopy Anchor Link

The stored size is 4n, but only O(log n) nodes are ever visited per operation — that gap between storage and touch is the magic trick.

Adding lazy propagationCopy Anchor Link

When updates change whole ranges instead of single cells, we can't afford to touch every leaf. Instead we drop a pending tag on the O(log n) nodes that represent the range, and push it down lazily:

function makeLazyTree(a) {  const n = a.length;  const tree = new Array(4 * n).fill(0);  const lazy = new Array(4 * n).fill(0);  const build = (node, l, r) => {    if (l === r) { tree[node] = a[l]; return; }    const mid = (l + r) >> 1;    build(2 * node, l, mid);    build(2 * node + 1, mid + 1, r);    tree[node] = tree[2 * node] + tree[2 * node + 1];  };  const push = (node, l, r) => {    if (lazy[node] === 0) return;    const mid = (l + r) >> 1;    const v = lazy[node];    tree[2 * node]     += v * (mid - l + 1);    tree[2 * node + 1] += v * (r - mid);    lazy[2 * node]     += v;    lazy[2 * node + 1] += v;    lazy[node] = 0;  };  const rangeAdd = (node, l, r, ql, qr, v) => {    if (qr < l || r < ql) return;    if (ql <= l && r <= qr) {      tree[node] += v * (r - l + 1);      lazy[node] += v;      return;    }    push(node, l, r);    const mid = (l + r) >> 1;    rangeAdd(2 * node, l, mid, ql, qr, v);    rangeAdd(2 * node + 1, mid + 1, r, ql, qr, v);    tree[node] = tree[2 * node] + tree[2 * node + 1];  };  build(1, 0, n - 1);  return { rangeAdd: (ql, qr, v) => rangeAdd(1, 0, n - 1, ql, qr, v) };}

Where you meet it todayCopy Anchor Link

• Databases and analytics. Column stores answer "sum/count over this time range" by reading precomputed aggregates per range. Indexed range scans are the same idea, one level up the stack.
• Graphics and geometry. The interval tree cousin answers "which shapes overlap this ray?" — exactly the stabbing query Bentley was chasing, and exactly how ray tracers and sweep-line renderers speed up intersection tests.
• Text editors and diffs. Counting changed lines across regions, or maintaining running statistics over an edit buffer, needs fast "aggregate over a range" plus edits.
• Competitive programming. Every "range min / range max / range sum with updates" problem has a segment tree at its heart — and most of them need the lazy version.

// Min over [l, r] — same skeleton, combine with Math.min instead of +function rmq(node, l, r, ql, qr) {  if (qr < l || r < ql) return Infinity;  if (ql <= l && r <= qr) return tree[node];  const mid = (l + r) >> 1;  return Math.min(    rmq(2 * node, l, mid, ql, qr),    rmq(2 * node + 1, mid + 1, r, ql, qr),  );}

RecapCopy Anchor Link

• A segment tree stores the aggregate of every nested range in a binary tree, giving O(log n) range queries and O(log n) updates — the balance prefix sums can't give.
• It lives in a flat 4n array; node i commands children 2i and 2i+1, covering the two halves of its range.
• The invariant is simple: each node equals combine of its children, so a fully-covered node can be returned whole and a query is a union of O(log n) such nodes.
• Lazy propagation extends the same skeleton to range updates by leaving pending tags on covered nodes and pushing them down only when needed.

Next up: Fenwick Trees (BIT) — the same range query, with a fraction of the memory and even less code.