Hvad er et prefix sum, og hvordan fremskynder det range queries?

Question

Accepted Answer

Et **prefix sum** array gemmer kumulative totaler, så ethvert **range sum** kan besvares i **O(1)** efter O(n) forbehandling — i stedet for O(n) pr. forespørgsel.

## Idéen

Lad `prefix[i]` være summen af de første `i` elementer. Så summen af `arr[l..r]` er `prefix[r+1] - prefix[l]`.

## Eksempel

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

## Spor

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

## Kompleksitet

- **Bygning:** O(n). **Forespørgsel:** O(1). **Plads:** O(n).

## Hvornår skal man bruge / Faldgruber

Ideal til **mange range-sum forespørgsler** på statiske data. Varianter: 2D prefix sums til submatrix-summer, prefix XOR og difference arrays til range-opdateringer. Hvis arrayet ændres ofte, brug i stedet en Fenwick/segment tree. Pas på index-offset (størrelse n+1).

## Hvorfor det betyder noget

Prefix sums omdanner gentagne O(n) range queries til O(1) opslag — en enorm gevinst når forespørgsler er hyppige.

Mønstret for at forbehandle en gang og give svar hurtigt generaliserer til mange databehandlingsopgaver.

Det er en grundpille i konkurrenceprogram og en hyppig byggesten i analytics.