سیگمنٹ ٹریز اور فینوک ٹریز (BIT) تیز رینج کویریز کو کیسے سپورٹ کرتے ہیں؟

Question

Accepted Answer

**سیگمنٹ ٹری** اور **فینوک ٹری** (بائنری انڈیکسڈ ٹری، BIT) دونوں **رینج کویریز** (مثال کے طور پر `[l, r]` پر رقم) اور **پوائنٹ اپڈیٹس** کو **O(log n)** میں جواب دیتے ہیں، بمقابلہ naive scan کے لیے O(n) یا prefix-sum array کے لیے 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) — کومپیکٹ اور eleگنٹ

```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)
```

## سیگمنٹ ٹری — زیادہ عام

ایک سیگمنٹ ٹری ایک بائنری ٹری میں ہر array سیگمنٹ کے لیے ایک aggregate محفوظ کرتا ہے، جو **کسی بھی associative operation** (sum، min، max، gcd) کو سپورٹ کرتا ہے اور lazy propagation کے ساتھ، **رینج اپڈیٹس** بھی کرتا ہے۔

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

## موازنہ

| | Fenwick (BIT) | Segment tree |
|---|---|---|
| Query / update | O(log n) | O(log n) |
| Space | O(n) | O(2n) |
| Operations | sums (invertible) | any associative op |
| Range updates | مشکل | آسان (lazy propagation) |
| Code size | بہت چھوٹا | بڑا |

## یہ کیوں اہم ہے

یہ structures "ایک value کو update کریں، پھر رینج کے اوپر ایک aggregate کی query کریں" کو تیز کرتے ہیں — competitive programming، analytics windows، اور interval problems کے لیے ضروری۔

ان میں سے انتخاب کریں یہ ایک trade-off ہے: ایک Fenwick tree بہت چھوٹا اور sums کے لیے تیز ہے، جبکہ ایک segment tree min/max/range-update workloads کے لیے زیادہ flexible ہے۔

	Fenwick (BIT)	Segment tree
Query / update	O(log n)	O(log n)
Space	O(n)	O(2n)
Operations	sums (invertible)	any associative op
Range updates	مشکل	آسان (lazy propagation)
Code size	بہت چھوٹا	بڑا