Segment Tree — The Template

Three recursive functions — build, query, update — and they all share the same skeleton: if my range is fully inside the target, act; if fully outside, stop; otherwise split and recurse. Learn that skeleton once and you can re-derive any of the three from scratch.

Try it

Run a query over a range and watch which nodes get used (strong purple) — that’s the O(log n) decomposition, never the full range of cells. Then update an index and watch only the root-to-leaf path change.

Try it — range-sum query and point update, both O(log n)

query [,]

set i=

The array representation

You don’t need real node objects with pointers. Store the tree in a flat array tree[] of size 2n to 4n, using the classic heap-style indexing:

node 1 is the root,
node k’s children are 2k (left) and 2k + 1 (right).

This is the same trick as the binary heap (Day 7) — implicit pointers via arithmetic. A size of 4n is always safe (the tree can be slightly unbalanced when n isn’t a power of two).

build — O(n)

Recurse down, splitting the range; at a leaf store the array value; on the way up, combine children.

query(i, j) — O(log n)

The three-case recursion: fully outside → identity; fully inside → stored value; partial → recurse both and combine.

update(i, v) — O(log n)

Recurse to the leaf for index i, set it, then recombine ancestors on the way back up.

To change the aggregate, change two lines. Want range minimum instead of sum? Replace every tree[2*node] + tree[2*node+1] with min(...), and the disjoint-case identity 0 with +∞ (INT_MAX). Max → use −∞. GCD → use 0 as identity (since gcd(0, x) = x). The skeleton never changes — only the combine function and its identity element. That’s the abstraction worth internalizing.

The shared skeleton

All three functions are the same recursion with different payloads:

Base case at the leaf / full-cover

build and update stop at a leaf; query stops when a node is fully inside the range.

Recurse into the relevant half / halves

update goes into the one half containing the index; query may go into both on a partial overlap; build always goes into both.

Combine on the way up

build and update recompute the parent from its children. query combines the partial results it gathered.

Quick check

In the array representation, node k's children are at indices 2k and 2k+1. Why allocate size 4n rather than 2n?

To convert this SUM segment tree into a MIN segment tree, what must change?

During update(idx, val), why does the recursion descend into only ONE child at each level, but build descends into both?

Next: Lazy Propagation — how to make range updates (“add 5 to every element in [i, j]”) O(log n) instead of O(n log n).

Introduction Lazy Propagation