Segment Tree

Brute force क्यों नहीं?

साधारण range-sum query पूरी range स्कैन करती है — प्रति query O(n)। Segment tree हिस्सों के sums को पहले से recursively गणना करता है, इसलिए कोई भी range query O(log n) बन जाती है। हर node एक उप-range का aggregate रखता है; leaves अकेले elements होते हैं।

बनाना और query करना

Tree को 4n आकार की array में रखें। build नीचे से ऊपर भरता है, query केवल overlapping हिस्सों में recurse करता है।

tree = [0] * (4 * n)

def build(node, lo, hi):
    if lo == hi:
        tree[node] = arr[lo]
        return
    mid = (lo + hi) // 2
    build(2*node, lo, mid)
    build(2*node+1, mid+1, hi)
    tree[node] = tree[2*node] + tree[2*node+1]

def query(node, lo, hi, l, r):
    if r < lo or hi < l:
        return 0
    if l <= lo and hi <= r:
        return tree[node]
    mid = (lo + hi) // 2
    return query(2*node, lo, mid, l, r) + query(2*node+1, mid+1, hi, l, r)

Output:

build(1, 0, n-1)
query(1, 0, n-1, 2, 5)  # sum of arr[2..5]

Point update

एक element अपडेट करने पर root से leaf तक के रास्ते के केवल O(log n) nodes प्रभावित होते हैं, फिर ऊपर आते हुए sums ठीक किए जाते हैं।

def update(node, lo, hi, idx, val):
    if lo == hi:
        tree[node] = val
        return
    mid = (lo + hi) // 2
    if idx <= mid:
        update(2*node, lo, mid, idx, val)
    else:
        update(2*node+1, mid+1, hi, idx, val)
    tree[node] = tree[2*node] + tree[2*node+1]

कब इस्तेमाल करें

Segment tree तब इस्तेमाल करें जब कई range queries updates के साथ interleaved हों — range-sum, range-min/max, या range-GCD भी। अगर updates कभी नहीं होते, तो साधारण prefix-sum array प्रति query O(1) और सरल है।