Kas yra prefiksų suma ir kaip ji pagreitina diapazonų užklausas?

Question

Accepted Answer

**Prefiksų sumos** masyvas saugo kumuliatyvias sumas, todėl bet kuri **diapazone sumos** užklausa gali būti atsakyta per **O(1)** po O(n) išankstinio apdorojimo — o ne O(n) per užklausą.

## Idėja

Tegu `prefix[i]` yra pirmųjų `i` elementų suma. Tada `arr[l..r]` suma yra `prefix[r+1] - prefix[l]`.

## Pavyzdys

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

## Trasavimas

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

## Sudėtingumas

- **Sukūrimas:** O(n). **Užklausa:** O(1). **Vieta:** O(n).

## Kada naudoti / pavojūs

Idealus **daugeliui diapazone sumų užklausų** statiniuose duomenyse. Variantai: 2D prefiksų sumos submatricų sumoms, prefiksų XOR ir skirtumo masyvai diapazone atnaujinimams. Jei masyvas keičiasi dažnai, naudokite Fenwick/segment medį. Stebėkite indekso poslinkį (dydis n+1).

## Kodėl tai svarbu

Prefiksų sumos paverčia pasikartojančias O(n) diapazone užklausas į O(1) paieškos — didžiulis pelnas, kai užklausų yra daug.

Išankstinis skaičiavimas kartą, greitai atsakykite šablonas apibendrina daugybę duomenų apdorojimo užduočių.

Tai pagrindinė konkurencinio programavimo elemento ir dažnas analitikos kūrimo blokas.