Lesson 2 � Advanced
Segment Tree: Range Queries
Segment Tree ek binary tree data structure hai jo arrays pe efficient range queries aur point updates karta hai. Prefix sum sirf prefix ke liye kaam karta hai, but segment tree kisi bhi range ke liye O(log n) mein answer deta hai!
Segment Tree hota kya hai?
WHAT
Segment Tree ek binary tree hai jismein har node array ke ek segment (range) ka result store karta hai. Root poora array represent karta hai, leaves single elements. Har node apne dono children ka combined result rakhta hai.
WHEN
Jab array pe baar baar range queries ho (range sum, range min/max) aur point updates bhi ho. Prefix sum O(1) query deta hai but O(n) update. Segment Tree dono O(log n) mein karta hai!
WHERE
Competitive coding mein bahut common � range queries, interval problems, 2D range queries. Real world mein stock prices ka range analysis, game scores tracking.
Visual: Segment Tree kaise banta hai
Array: [1, 3, 5, 7, 9, 11]
[36] ✓ total sum (0-5)
/ \
[9] [27] ✓ sum of halves
/ \ / \
[4] [5] [16] [11] ✓ sum of quarters
/ \ / \ / \ \
[1][3][5][7][9][11] ✓ leaves (original array)
Har node ek range ka sum store karta hai:
Node [36] = range(0,5) = 1+3+5+7+9+11 = 36
Node [9] = range(0,2) = 1+3+5 = 9
Node [27] = range(3,5) = 7+9+11 = 27
Node [4] = range(0,1) = 1+3 = 4
Node [16] = range(3,4) = 7+9 = 16
Query: sum(1,4) = ?
Path: range(1,4) = range(0,2)[1,2] + range(3,4)[3,4]
= (3+5) + (7+9) = 24 ?Build the Segment Tree
def build(arr, node, start, end):
if start == end:
# Leaf node � single element
tree[node] = arr[start]
else:
mid = (start + end) // 2
# Left child: range(start, mid)
build(arr, 2 * node + 1, start, mid)
# Right child: range(mid+1, end)
build(arr, 2 * node + 2, mid + 1, end)
# Parent = sum of children
tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
# Usage
arr = [1, 3, 5, 7, 9, 11]
n = len(arr)
tree = [0] * (4 * n) # 4*n space sufficient
build(arr, 0, 0, n - 1)
print(tree) # [36, 9, 27, 4, 5, 16, 11, 1, 3, 5, 7, 9, 11]Range Query
def query(node, start, end, l, r):
# Query range [l, r] se overlap nahi karta
if r < start or end < l:
return 0
# Query range poora cover karta hai
if l <= start and end <= r:
return tree[node]
# Partial overlap � dono sides check karo
mid = (start + end) // 2
left_sum = query(2 * node + 1, start, mid, l, r)
right_sum = query(2 * node + 2, mid + 1, end, l, r)
return left_sum + right_sum
# Usage: sum of range [1, 4]
print(query(0, 0, n - 1, 1, 4)) # 3+5+7+9 = 24Point Update
def update(node, start, end, idx, val):
if start == end:
# Leaf node � value update karo
tree[node] = val
else:
mid = (start + end) // 2
if idx <= mid:
update(2 * node + 1, start, mid, idx, val)
else:
update(2 * node + 2, mid + 1, end, idx, val)
tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
# Usage: arr[2] = 10 update karo
update(0, 0, n - 1, 2, 10)
print(query(0, 0, n - 1, 0, 5)) # new total sumSegment Tree ke Types
# Range Sum Query
def combine_sum(left, right):
return left + right
# Range Minimum Query
def combine_min(left, right):
return min(left, right)
# Range Maximum Query
def combine_max(left, right):
return max(left, right)
# GCD Query
from math import gcd
def combine_gcd(left, right):
return gcd(left, right)
# Har type ke liye same structure hai,
# sirf combine function alag hai!Try it: code khud likho
Exercise
Question: Array [2, 4, 6, 8, 10] pe segment tree banao. Range [1, 3] ka sum kya hai✓ Answer mein number daalo.
Question: Array ke n elements ke liye segment tree mein kitni space lagti hai (approximate)✓ Answer mein formula daalo (n ke terms mein).
Common mistakes
- Tree size insufficient: Segment tree ke liye
4 * nspace lo.2 * nkabhi kabhi kam pad jaata hai especially jab skewed tree bane. - Off-by-one in ranges: Query function mein
r < startvsr <= startyaend < lvsend <= l. Zero-based indexing mein ranges inclusive hain � dhyan se check karo. - Update function mein lazy propagation na karna: Agar range updates bhi chahiye (sirf point nahi), toh Lazy Propagation use karo. Basic segment tree sirf point update karta hai efficiently.
- Combine function associativity: Segment tree tabhi kaam karta hai jab combine function associative ho �
(a+b)+c = a+(b+c). Min, max, sum, GCD sab associative hain. BUT subtraction nahi hai!
Segment Tree samajh aa gaya✓ Ab Bit Manipulation dekhte hain � ye tricks interview mein bahut kaam aati hain!