સેગમેન્ટ ટ્રીઝ અને ફેનવિક ટ્રીઝ (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)
કોડ કદ	ખૂબ જ નાનું	મોટું