Overview
Segment tree data structure hai jo O(log n) range queries (min/max/sum) aur O(log n) point updates support karta hai.
Analogy
Jaise sub-departments wali organizational hierarchy—root se kisi bhi department ki stats track kar sakte hain.
Step-by-step
- Subarray sum/min/max store karne wala tree build karo
- Node i: children 2i (left) aur 2i+1 (right)
- Query: range contain karne wale children par recurse karo
- Point update: leaf update karo aur upar propagate karo
Visual
arr=[1,3,2,7,9,11]
Nodes: [33,11,22,4,7,20,2,1,3,2,7,9,11]
sum(2,5)=2+7+9+11=29
Common mistakes
- Array size: 4*n safe hai (2n kuch cases mein insufficient)
- Index offset (1-based vs 0-based) confusion
Practice questions
- Sum segment tree implement karo
- Lazy propagation se range update implement karo
Time
O(log n) query aur update