# Segment Tree — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/segment-tree

> Array पर बना binary tree जो range queries (sum, min, max) और point updates को O(log n) में हल करता है।

## 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 करता है।

```python
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 ठीक किए जाते हैं।

```python
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)` और सरल है।