முன்னொட்டு தொகை என்றால் என்ன, மேலும் அது வரம்பு வினாக்களை எவ்வாறு துரிதப்படுத்துகிறது?

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) தேடல்களாக மாற்றுகின்றன — வினாக்கள் அடிக்கடி இருக்கும்போது பெரும் வெற்றி.

ஒருமுறை முன்கணக்கிட்டு வேகமாக பதிலளிக்கும் வடிவம் பல தரவு-செயலாக்கப் பணிகளுக்குப் பொதுமைப்படுத்தப்படுகிறது.

இது போட்டி நிரலாக்கத்தின் ஒரு பகுதி மற்றும் பகுப்பாய்வின் ஒரு பொதுவான கட்டிடத் தொகுதி.