ఉపసర্గ సమ్ మంటే ఏమిటి, మరియు ఇది పరిధి ప్రశ్నలను ఎలా వేగవంతం చేస్తుంది?

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/సెగ్‌మెంట్ చెట్టు ఉపయోగించండి. సూచిక ఆఫ్‌సెట్ గురించి జాగ్రత్త వహించండి (పరిమాణం n+1).

## ఎందుకు ముఖ్యమైనది

ఉపసర్గ సమ్‌లు పునరావృత O(n) పరిధి ప్రశ్నలను O(1) శోధనలుగా మారుస్తాయి — ప్రశ్నలు తరచుగా ఉన్నప్పుడు పెద్ద విజయం.

ఒకసారి ప్రీకంప్యూట్ మరియు వేగంగా సమాధానమివ్వే నమూనా అనేక డేటా-ప్రాసెసింగ్ పనులకు సాధారణీకరిస్తుంది.

ఇది పోటీ ప్రోగ్రామింగ్ యొక్క ప్రధానమైనది మరియు విశ్లేషణలో సాధారణ బిల్డింగ్ బ్లాక్.