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

Question

IT Interview Practice · 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.

Idėja

Pavyzdys

Trasavimas

Sudėtingumas

Kada naudoti / pavojūs

Kodėl tai svarbu

Susiję klausimai