सेगमेंट ट्रीज़ और फेनविक ट्रीज़ (BIT) तेज़ रेंज क्वेरीज़ को कैसे समर्थन देते हैं?

Question

Accepted Answer

एक **सेगमेंट ट्री** और एक **फेनविक ट्री** (Binary Indexed Tree, BIT) दोनों ही **रेंज क्वेरीज़** (उदा. `[l, r]` पर योग) और **पॉइंट अपडेट्स** को **O(log n)** में जवाब देते हैं, जो सरल स्कैन के O(n) या प्रीफिक्स-सम ऐरे के O(n) अपडेट्स की तुलना में है।

## समस्या जिसे वे हल करते हैं

```text
Array + many "sum of range [l,r]" and "update index i" calls:
  naive prefix sums: query O(1) but UPDATE is O(n)
  segment/Fenwick:   query O(log n) AND update O(log n)
```

## फेनविक ट्री (BIT) — संक्षिप्त और सुंदर

```python
class Fenwick:
    def __init__(self, n):
        self.t = [0]*(n+1)
    def update(self, i, delta):        # O(log n)
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & (-i)              # jump to next responsible node
    def prefix(self, i):               # sum of [0..i], O(log n)
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & (-i)
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l-1)
```

## सेगमेंट ट्री — अधिक सामान्य

एक सेगमेंट ट्री एक बाइनरी ट्री में ऐरे सेगमेंट के अनुसार एग्रीगेट स्टोर करता है, जो **कोई भी एसोशिएटिव ऑपरेशन** (योग, न्यूनतम, अधिकतम, gcd) समर्थन करता है और, आलस प्रसार के साथ, **रेंज अपडेट्स** भी।

```text
        [0..7] sum
       /          \
   [0..3]         [4..7]
   /    \         /    \
 [0..1][2..3]  [4..5][6..7]   ... down to single elements
```

## तुलना

| | फेनविक (BIT) | सेगमेंट ट्री |
|---|---|---|
| क्वेरी / अपडेट | O(log n) | O(log n) |
| स्पेस | O(n) | O(2n) |
| ऑपरेशन्स | योग (उल्टे) | कोई भी एसोशिएटिव ऑप |
| रेंज अपडेट्स | कठिन | आसान (lazy propagation) |
| कोड साइज़ | बहुत छोटा | बड़ा |

## यह क्यों महत्वपूर्ण है

ये संरचनाएं "एक मान को अपडेट करें, फिर किसी रेंज पर एग्रीगेट को क्वेरी करें" को तेज़ बनाती हैं — प्रतिस्पर्धी प्रोग्रामिंग, विश्लेषण विंडो और अंतराल समस्याओं के लिए आवश्यक।

उनके बीच चुनना एक ट्रेड-ऑफ है: फेनविक ट्री योग के लिए छोटा और तेज़ है, जबकि सेगमेंट ट्री न्यूनतम/अधिकतम/रेंज-अपडेट कार्यभार के लिए अधिक लचीला है।

	फेनविक (BIT)	सेगमेंट ट्री
क्वेरी / अपडेट	O(log n)	O(log n)
स्पेस	O(n)	O(2n)
ऑपरेशन्स	योग (उल्टे)	कोई भी एसोशिएटिव ऑप
रेंज अपडेट्स	कठिन	आसान (lazy propagation)
कोड साइज़	बहुत छोटा	बड़ा