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

Question

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) — فائدة كبيرة عندما تكون الاستعلامات متكررة.

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

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