Kaj je vsota predslovke in kako pospešuje poizvedbe po obsegih?

Question

Accepted Answer

Niz **vsota predslovke** shranjuje skupne vsote, tako da je mogoče katero koli **vsoto obsega** odgovoriti v **O(1)** po O(n) predprocesiranju — namesto O(n) na poizvedbo.

## Ideja

Pustite, da je `prefix[i]` vsota prvih `i` elementov. Potem je vsota `arr[l..r]` enaka `prefix[r+1] - prefix[l]`.

## Primer

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

## Sled

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

## Kompleksnost

- **Gradnja:** O(n). **Poizvedka:** O(1). **Prostor:** O(n).

## Kdaj uporabiti / Pasti

Idealna za **več poizvedb za vsoto obsega** na statičnih podatkih. Različne različice: 2D vsote predslovke za vsote podmatrike, predslovka XOR in nizi razlik za posodobitve obsega. Če se niz pogosto spreminja, namesto tega uporabite Fenwick/segment tree. Pazite na odmik indeksa (velikost n+1).

## Zakaj je to pomembno

Vsote predslovke spremenijo ponovljene poizvedbe O(n) v O(1) poizvedbe — ogromna zmaga, kadar so poizvedbe pogoste.

Vzorec enkratnega predračunavanja in hitrega odgovarjanja se posplošuje na mnoge naloge obdelave podatkov.

To je stalnica konkurenčnega programiranja in običajni gradnik v analitiki.