Mi az előtag-összeg, és hogyan gyorsítja fel a tartománylekérdezéseket?

Question

Accepted Answer

Az **előtag-összeg** tömb kumulatív összegeket tárol, így bármely **tartomány-összeg** O(n) előfeldolgozás után **O(1)** időben megválaszolható — kérdésenként O(n) helyett.

## Az ötlet

Legyen `prefix[i]` az első `i` elem összege. Ekkor az `arr[l..r]` összege `prefix[r+1] - prefix[l]`.

## Példa

```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
```

## Nyomkövetés

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Bonyolultság

- **Építés:** O(n). **Lekérdezés:** O(1). **Hely:** O(n).

## Mikor használjuk / csapdák

Ideális **számos tartomány-összeg lekérdezéshez** statikus adatokon. Változatok: 2D előtag-összegek almatrix-összegekhez, előtag XOR és különbség tömbök tartománybeli frissítésekhez. Ha a tömb gyakran változik, használjon helyette Fenwick/szegment fát. Ügyeljen az index eltolódásra (méret n+1).

## Miért számít

Az előtag-összegek az ismétlődő O(n) tartománylekérdezéseket O(1) keresésekre alakítják — hatalmas előny, ha a lekérdezések gyakran fordulnak elő.

Az egyszer előszámítás, gyorsan válaszolás minta számos adatfeldolgozási feladatra általánosítható.

A versenyfeladatok alapja és az analitika közös építőköve.