खण्ड रुखहरु (segment trees) र फेनविक रुखहरु (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) |
| संचालनहरु | योगहरु (उल्टो गरिएको) | कुनै पनि सहयोगी सञ्चालन |
| दायरा अपडेटहरु | कठिन | सजिलो (आलस प्रसार) |
| कोड आकार | साना | ठूलो |

## यो किन महत्त्वपूर्ण छ

यी संरचनाहरुले "मान अपडेट गर्नुहोस्, त्यसपछि दायरामा एक समग्र प्रश्न गर्नुहोस्" द्रुत बनाउँछन् — प्रतिस्पर्धी प्रोग्रामिङ्ग, विश्लेषण विन्डोहरु, र अन्तराल समस्याहरुको लागि आवश्यक।

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

	फेनविक (BIT)	खण्ड रुख
प्रश्न / अपडेट	O(log n)	O(log n)
स्पेस	O(n)	O(2n)
संचालनहरु	योगहरु (उल्टो गरिएको)	कुनै पनि सहयोगी सञ्चालन
दायरा अपडेटहरु	कठिन	सजिलो (आलस प्रसार)
कोड आकार	साना	ठूलो