ما هو المجموع البادئ (prefix sum)، وكيف يسرع الاستعلامات عن النطاقات؟

Question

IT Interview Practice · Accepted Answer

مصفوفة **المجموع البادئ** تخزن المجاميع التراكمية بحيث يمكن الإجابة عن أي **مجموع نطاق** في **O(1)** بعد معالجة O(n) — بدلاً من O(n) لكل استعلام.

## الفكرة

لتكن `prefix[i]` المجموع الأول من العناصر `i`. ثم مجموع `arr[l..r]` هو `prefix[r+1] - prefix[l]`.

## مثال

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## تتبع

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## التعقيد

- **البناء:** O(n). **الاستعلام:** O(1). **المساحة:** O(n).

## متى يتم الاستخدام / التحديات

مثالي للعديد من **استعلامات مجموع النطاق** على البيانات الثابتة. المتغيرات: مجاميع البادئة ثنائية الأبعاد لمجاميع المصفوفة الجزئية، XOR البادئة، ومصفوفات الفروقات لتحديثات النطاق. إذا تغيرت المصفوفة بشكل متكرر، استخدم Fenwick أو segment tree بدلاً من ذلك. انتبه لإزاحة الفهرس (الحجم n+1).

## لماذا يهم

تحول المجاميع البادئة استعلامات O(n) المتكررة إلى بحث O(1) — فائدة كبيرة عندما تكون الاستعلامات متكررة.

يعمم نمط الحساب المسبق والإجابة السريعة على العديد من مهام معالجة البيانات.

إنها أساسية في البرمجة التنافسية وكتلة بناء شائعة في التحليلات.

الفكرة

مثال

تتبع

التعقيد

متى يتم الاستخدام / التحديات

لماذا يهم

أسئلة ذات صلة