Vad är en prefiksumma och hur påskyndar det intervallfrågor?

Question

Accepted Answer

En **prefiksumma**-array lagrar kumulativa totaler så att vilken **intervallfråga** som helst kan besvaras i **O(1)** efter O(n) förbehandling — istället för O(n) per fråga.

## Idén

Låt `prefix[i]` vara summan av de första `i` elementen. Då är summan av `arr[l..r]` lika med `prefix[r+1] - prefix[l]`.

## Exempel

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

## Spårning

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

## Komplexitet

- **Bygga:** O(n). **Fråga:** O(1). **Utrymme:** O(n).

## När använd / Fallgropar

Ideal för **många intervallfrågor** på statisk data. Varianter: 2D-prefiksummor för submatrisummor, prefix XOR och differensarrayer för intervallupdateringar. Om arrayen ändras ofta använder du ett Fenwick/segmentträd istället. Observera indexoffset (storlek n+1).

## Varför det spelar roll

Prefiksummor förvandlar återstödda O(n) intervallfrågor till O(1) uppslagningar — en stor vinst när frågorna är frekventa.

Mönstret förberäkna-en-gång-och-svar-snabbt generaliseras till många databehandlingsuppgifter.

Det är en grundläggande teknik inom tävlingsprogrammering och en vanlig byggsten inom analys.