प्रीफिक्स सम म्हणजे काय, आणि ते रेंज क्वेरी कसे गती देते?

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 tree वापरा. इंडेक्स ऑफसेट लक्षात ठेवा (आकार n+1).

## हे महत्वाचे कारण

प्रीफिक्स सम्स पुनरावृत्त O(n) रेंज क्वेरीज O(1) लुकअप्समध्ये बदलते — क्वेरीज वारंवार असताना मोठा जिंकणे.

प्रीकम्प्यूट-एकदा, उत्तर-वेगवान पॅटर्न अनेक डेटा-प्रोसेसिंग टास्क्सला सामान्यीकृत करते.

हा स्पर्धा प्रोग्रामिंगचा मुख्य घटक आणि विश्लेषणातील सामान्य बिल्डिंग ब्लॉक आहे.