Foundations — Segment tree — build, range query, point update

This page assumes you know nothing about segment trees. Every letter, bracket, and arrow the parent note uses is built here, one at a time, each resting on the previous.

0. The array — the thing we are storing

Look at the figure: the box labelled a[0] holds 2, the box a[2] holds 5. The little number under each box (0, 1, 2, 3) is its index; the number inside is its value.

• The symbol a[i] is read "a at i" — the value stored at index i.
• n is the number of boxes (here n = 4), so the valid indices run 0, 1, ..., n-1.

1. A range [lo, hi] — a contiguous slice

The picture below shades the range $[1,2]$ in red. Notice it is contiguous — no gaps. Segment trees only ever deal with contiguous ranges; that is what makes the cut-in-half trick work.

• $lo$ = the lowest index in the slice.
• $hi$ = the highest index in the slice.
• The parent question "sum of a[l..r]?" uses l and r as the query's low and high. Same idea, different letters: l is a lo, r is a hi.
• A range with $lo=hi$ (like $[2,2]$) is a single box — the smallest possible range.

2. Splitting a range — the midpoint $mid$

Two new symbols to earn here:

• $\lfloor \rfloor$ is the floor — "round down to the nearest whole number". So $\lfloor 3.5\rfloor =3$. We need it because $\frac{lo+hi}{2}$ can be a fraction, but an index must be a whole number.
• The two halves never overlap and cover everything: the left ends at $mid$, the right starts at $mid+1$. No box is counted twice, none is left out.

3. The logarithm ${\log }_{2}n$ — how many halvings?

• The parent writes $O(\log n)$ for query and update speed. That $\log n$ is exactly the number of levels in the tree — the number of halvings from the whole array down to one box.
• $\lceil \rceil$ is the ceiling — "round up". The tree's height is $\lceil {\log }_{2}n\rceil$ because a fractional number of levels still needs a whole extra level.

4. A binary tree — halves inside halves

Map this straight onto ranges:

• The root is the whole range $[0,n-1]$.
• Each node's two children are its left half and right half.
• A leaf is a single box $[i,i]$ — it cannot split further.

So the tree is the family history of splits from Section 2. Nothing new — just a name for the picture of halves-within-halves.

5. Heap indexing — a tree living in a flat array

We do not build the tree with pointers. We store it in one flat array tree[] and use arithmetic to move around it. This trick comes from the Heap.

• v is just the name of a node = its slot number in tree[]. When the code says build(2*v, ...) it means "go handle my left child."
• tree[v] is the stored answer for whatever range node v covers.

6. Combine and identity — gluing two answers

• The parent's "no overlap → return 0" returns this identity, so an empty contribution safely folds into the total.
• For min the identity is $+\infty$; for max it is $-\infty$; for product it is 1. Same skeleton, different glue — which is why the topic keeps saying "identity" rather than literally "0".

7. Big-O notation $O(\cdot )$ — measuring cost

The whole point of the topic is trading a slow cost for a fast one:

Compare with cousins: Prefix Sum gives $O(1)$ queries but $O(n)$ updates; Fenwick Tree (BIT) matches the segment tree's $O(\log n)$/$O(\log n)$ with less code but less flexibility; Lazy Propagation extends the tree to fast range updates.

The prerequisite map

Equipment checklist