Segment tree — build, range query, point update

WHY does it exist?

Suppose you have an array and must support both:

Range query — "sum of a[l..r]?"
Point update — "set a[i] = x".

Approach	Query	Update
Plain array	$O(n)$	$O(1)$
Prefix sums	$O(1)$	$O(n)$ (rebuild)
Segment tree	$O(\log n)$	$O(\log n)$

We store it in a flat array tree[] using the heap indexing trick: node at index v has children 2v and 2v+1, root at index 1. A size- $n$ array needs a tree[] of size $==4n==$ to be safe.

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

HOW: derive each operation from scratch

1. Build — $O(n)$

We define build(v, lo, hi) = fill node v knowing it covers [lo,hi].

def build(v, lo, hi):
    if lo == hi:
        tree[v] = a[lo]
        return
    mid = (lo + hi) // 2
    build(2*v,   lo,    mid)   # left child
    build(2*v+1, mid+1, hi)    # right child
    tree[v] = tree[2*v] + tree[2*v+1]

Why $O(n)$ ? Each array element appears in exactly one leaf, and the tree has $2n-1$ nodes total, each touched once.

2. Range query `query(l, r)` — $O(\log n)$

Define query(v, lo, hi, l, r) = sum over the intersection of the node's range [lo,hi] with the wanted range [l,r].

def query(v, lo, hi, l, r):
    if r < lo or hi < l:          # no overlap
        return 0
    if l <= lo and hi <= r:       # total overlap
        return tree[v]
    mid = (lo + hi) // 2          # partial overlap
    return query(2*v, lo, mid, l, r) + query(2*v+1, mid+1, hi, l, r)

Why $O(\log n)$ ? Key fact: at each level of the tree, at most 4 nodes are visited (2 fully expand near the left boundary, 2 near the right). With $\log n$ levels → $O(\log n)$ work.

3. Point update `update(i, val)` — $O(\log n)$

Set a[i] = val and fix every ancestor.

def update(v, lo, hi, i, val):
    if lo == hi:                  # reached the leaf for index i
        tree[v] = val
        return
    mid = (lo + hi) // 2
    if i <= mid:
        update(2*v,   lo,    mid, i, val)
    else:
        update(2*v+1, mid+1, hi, i, val)
    tree[v] = tree[2*v] + tree[2*v+1]   # repair on the way up

Why $O(\log n)$ ? Only the single root-to-leaf path (length $\le \log n$ ) changes; every other node still holds a correct value.

Common mistakes (Steel-manned)

Flashcards

What does each node of a segment tree store?

The answer (e.g. sum) for a contiguous range of the underlying array.

Why size

4n

for the tree[] array?

Heap indexing on non-power-of-2

n

can use indices up to nearly

4n

;

4n

is a safe over-allocation.

Three cases of a range query?

No overlap → return identity; total overlap → return node value (stop); partial overlap → recurse both children and combine.

Time complexity of build, query, update?

O(n)

O(\log n)

O(\log n)

In heap indexing, children of node v?

2v and 2v+1, with root at index 1.

Why is query

O(\log n)

not

O(n)

Total-overlap nodes return immediately; at most 4 nodes per level expand, over

\log n

levels.

After a point update, which nodes need recomputing?

Only the ancestors on the root-to-leaf path of the updated index.

What must "no overlap" return for a min segment tree?

+\infty

(the identity of min), not 0.

Recurrence for an internal node's value (sum tree)?

tree[v] = tree[2v] + tree[2v+1].

Why do prefix sums lose to segment trees here?

A single update forces an

O(n)

prefix rebuild; segment tree update is

O(\log n)

Recall Feynman: explain to a 12-year-old

Imagine a long row of jars with coins. You keep asking "how many coins from jar 4 to jar 9?" Counting every time is slow. So you build a pyramid of helper boxes: at the bottom each box knows one jar's count; one level up, a box knows the total of two jars; higher boxes know bigger groups; the top box knows everything. To answer "jars 4 to 9", you grab a few already-filled boxes that exactly cover 4–9 — never counting jar by jar. If someone changes one jar, you only fix the boxes sitting directly above it (a single path up the pyramid), not the whole thing. That's a segment tree.

Connections

Binary Tree — segment tree is a complete binary tree over array ranges.
Heap — shares the 2v / 2v+1 flat-array indexing.
Prefix Sum — the static alternative; loses on updates.
Fenwick Tree (BIT) — lighter structure for prefix-sum-style queries.
Lazy Propagation — extension for $O(\log n)$ range updates.
Divide and Conquer — build/query are textbook divide-and-conquer.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tumhare paas ek array hai aur tumse baar-baar poocha jaata hai "l se r tak ka sum kitna hai?" aur beech-beech mein koi element change bhi karta rehta hai. Har baar pura array scan karna slow hai ( $O(n)$ ), aur prefix sum se query toh fast ho jaati hai par ek update pe pura prefix dobara banana padta hai. Yahin segment tree kaam aata hai — ek binary tree jisme har node ek range ka answer (jaise sum) store karta hai. Root pura array cover karta hai, neeche jaate jaate range aadhi-aadhi hoti jaati hai, aur leaf sirf ek element rakhta hai.

Build post-order mein hota hai: pehle dono bachche banao, phir parent = left + right. Yeh $O(n)$ hai kyunki total nodes $2n-1$ hote hain. Query mein teen cases yaad rakho — None, All, Split: agar node ki range query se bahar hai toh identity (sum ke liye 0) return karo; agar node poori query ke andar hai toh seedha stored value return karo aur ruk jao; agar aadha-aadha overlap hai toh dono bachchon mein recurse karke jod do. Yeh "All" wala case hi speedup deta hai, isliye $O(\log n)$ .

Update mein root se leaf tak jao, leaf ka value set karo, aur wapas aate waqt har ancestor ko left + right se dobara compute karo — sirf ek path change hota hai, isliye $O(\log n)$ .

Do galtiyan jo sab karte hain: (1) tree array ka size $2n$ rakhna — non-power-of-2 $n$ pe index overflow ho jaata hai, isliye hamesha $4n$ lo. (2) "No overlap" mein hamesha 0 return karna — yeh sirf sum ke liye theek hai; min ke liye $+\infty$ chahiye. Yeh chhoti baatein interview aur contest dono mein bachaati hain.

Segment tree — build, range query, point update

WHY does it exist?

WHAT is the structure?

HOW: derive each operation from scratch

1. Build — $O(n)$

2. Range query `query(l, r)` — $O(\log n)$

3. Point update `update(i, val)` — $O(\log n)$

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections