Segment tree — build, range query, point update

3.4.15 · Coding › Trees

YE EXIST KYUN KARTA HAI?

Maano tumhare paas ek array hai aur tumhe dono support karne hain:

Range query — "a[l..r] ka sum kya hai?"
Point update — "a[i] = x set karo".

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

Hum ise ek flat array tree[] mein heap indexing trick se store karte hain: index v wale node ke children 2v aur 2v+1 hote hain, root index 1 par hota hai. Size- $n$ array ke liye tree[] ka size safe rehne ke liye $== 4 n ==$ chahiye.

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

KAISE: har operation ko scratch se derive karo

1. Build — $O (n)$

Hum build(v, lo, hi) define karte hain = node v ko fill karo yeh jaante hue ki ye [lo,hi] cover karta hai.

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]

$O (n)$ kyun? Har array element exactly ek leaf mein appear karta hai, aur tree mein total $2 n - 1$ nodes hain, har ek sirf ek baar touch hota hai.

2. Range query `query(l, r)` — $O (lo g n)$

query(v, lo, hi, l, r) define karo = node ke range [lo,hi] aur wanted range [l,r] ke intersection par sum.

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)

$O (lo g n)$ kyun? Key fact: tree ke har level par at most 4 nodes visit hote hain (2 left boundary ke paas fully expand hote hain, 2 right ke paas). $lo g n$ levels ke saath → $O (lo g n)$ work.

3. Point update `update(i, val)` — $O (lo g n)$

a[i] = val set karo aur har ancestor fix karo.

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

$O (lo g n)$ kyun? Sirf single root-to-leaf path (length $\leq lo g n$ ) change hota hai; baaki har node abhi bhi correct value hold karta hai.

Common mistakes (Steel-manned)

Flashcards

Segment tree ke har node mein kya store hota hai?

Underlying array ke ek contiguous range ka answer (jaise sum).

tree[] array ka size

4 n

kyun?

Non-power-of-2

n

par heap indexing nearly

4 n

tak indices use kar sakta hai;

4 n

ek safe over-allocation hai.

Range query ke teen cases kya hain?

No overlap → identity return karo; total overlap → node value return karo (ruko); partial overlap → dono children mein recurse karo aur combine karo.

Build, query, update ki time complexity?

O (n)

O (lo g n)

O (lo g n)

Heap indexing mein node v ke children kya hain?

2v aur 2v+1, root index 1 par.

Query

O (lo g n)

kyun hai

O (n)

nahi?

Total-overlap nodes immediately return karte hain; har level par at most 4 nodes expand hote hain,

lo g n

levels ke upar.

Point update ke baad kaun se nodes recompute karne padte hain?

Sirf updated index ke root-to-leaf path par wale ancestors.

Min segment tree mein "no overlap" kya return karna chahiye?

+ \infty

(min ka identity), 0 nahi.

Internal node ki value ka recurrence (sum tree)?

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

Prefix sums segment trees se yahan kyun haarte hain?

Ek single update

O (n)

prefix rebuild force karta hai; segment tree update

O (lo g n)

hai.

Recall Feynman: 12-saal ke bacche ko samjhao

Socho ek lambi katar mein sikkon se bhari botalein hain. Tum baar baar poochh rahe ho "bottal 4 se bottal 9 tak kitne sikke hain?" Har baar count karna slow hai. Toh tum pyramid of helper boxes banate ho: neeche har box ek bottal ka count jaanta hai; ek level upar, ek box do botalon ka total jaanta hai; upar wale boxes bade groups jaante hain; top box sab jaanta hai. "Botalein 4 se 9" ka jawab dene ke liye, tum kuch pehle se bhari boxes uthao jo exactly 4–9 cover karti hain — jar by jar count kabhi nahi. Agar koi ek bottal change kare, tum sirf seedha uske upar wali boxes fix karte ho (pyramid mein ek hi path), poori cheez nahi. Yahi segment tree hai.

Connections

Binary Tree — segment tree array ranges par ek complete binary tree hai.
Heap — 2v / 2v+1 flat-array indexing share karta hai.
Prefix Sum — static alternative; updates par haarta hai.
Fenwick Tree (BIT) — prefix-sum-style queries ke liye lighter structure.
Lazy Propagation — $O (lo g n)$ range updates ke liye extension.
Divide and Conquer — build/query textbook divide-and-conquer hain.