접두사 સરવાળો શું છે અને તે શ્રેણી પ્રશ્નોને કેવી રીતે ઝડપ આપે છે?

Question

Accepted Answer

**接첫사 સરવાળો** એરે સંચિત કુલ સંગ્રહ કરે છે તેથી કોઈપણ **શ્રેણી સરવાળો** O(n) પ્રીપ્રોસેસિંગ પછી **O(1)** માં જવાબ આપી શકાય — પ્રતિ પ્રશ્ન 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).

## ક્યારે ઉપયોગ કરવો / પિતૃઓ

સ્ટેટિક ડેટા પર **ઘણા શ્રેણી-સરવાળો પ્રશ્નો** માટે આદર્શ। વેરિઅન્ટ્સ: સબમેટ્રિક્સ સરવાળા માટે 2D 접두사 સરવાળો, 접두사 XOR, અને શ્રેણી અપડેટ માટે તફાવત એરે। જો એરે વારંવાર બદલાય, તો તેના બદલે Fenwick/segment ટ્રી વાપરો। ઇન્ડેક્સ ઓફસેટ (સાઈઝ n+1) જોશો.

## શા માટે તે મહત્વપૂર્ણ છે

접두사 સરવાળો પુનરાવર્તિત O(n) શ્રેણી પ્રશ્નોને O(1) લુકઅપમાં ફેરવે છે — જ્યારે પ્રશ્નો વારંવાર હોય તો મોટો જીત।

પ્રીકમ્પ્યુટ-એક-વાર, જવાબ-ફાસ્ટ પેટર્ન ઘણા ડેટા-પ્રોસેસિંગ કાર્યો માટે સામાન્ય થાય છે।

તે સ્પર્ધાત્મક પ્રોગ્રામિંગ એક મુખ્યસ્થાન છે અને વિશ્લેષણમાં એક સામાન્ય બિલ્ડિંગ બ્લોક છે।