كيف تدعم أشجار القطاعات (Segment Trees) وأشجار Fenwick (BIT) الاستعلامات السريعة على النطاقات؟

Question

IT Interview Practice · Accepted Answer

يجيب **شجرة القطاع** و**شجرة Fenwick** (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)
```

## شجرة Fenwick (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
```

## المقارنة

| | Fenwick (BIT) | شجرة القطاع |
|---|---|---|
| الاستعلام / التحديث | O(log n) | O(log n) |
| المساحة | O(n) | O(2n) |
| العمليات | مجاميع (قابلة للعكس) | أي عملية ترابطية |
| تحديثات النطاق | أصعب | سهل (الانتشار الكسول) |
| حجم الكود | صغير جدًا | أكبر |

## لماذا يهمك

تجعل هذه الهياكل "تحديث قيمة، ثم الاستعلام عن مجموع على نطاق" سريعًا — وهذا ضروري للبرمجة التنافسية ونوافذ التحليلات ومشاكل الفترات.

الاختيار بينهما هو مقايضة: شجرة Fenwick صغيرة وسريعة للمجاميع، بينما شجرة القطاع أكثر مرونة لأحمال العمل min/max/تحديثات النطاق.

	Fenwick (BIT)	شجرة القطاع
الاستعلام / التحديث	O(log n)	O(log n)
المساحة	O(n)	O(2n)
العمليات	مجاميع (قابلة للعكس)	أي عملية ترابطية
تحديثات النطاق	أصعب	سهل (الانتشار الكسول)
حجم الكود	صغير جدًا	أكبر

المشكلة التي يحلانها

شجرة Fenwick (BIT) — مدمجة وأنيقة

شجرة القطاع — أكثر عمومية

المقارنة

لماذا يهمك

أسئلة ذات صلة