Czym jest suma prefiksowa i jak przyspiesza zapytania na zakresach?

Question

Accepted Answer

Tablica **prefix sum** przechowuje skumulowane sumy, dzięki czemu dowolna **range sum** można odpowiedzieć w **O(1)** po O(n) preprocessingu — zamiast O(n) na zapytanie.

## Ideę

Niech `prefix[i]` będzie sumą pierwszych `i` elementów. Wówczas suma `arr[l..r]` to `prefix[r+1] - prefix[l]`.

## Przykład

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

## Ślad

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

## Złożoność

- **Budowa:** O(n). **Zapytanie:** O(1). **Pamięć:** O(n).

## Kiedy używać / pułapki

Idealna dla **wielu zapytań range-sum** na danych statycznych. Warianty: 2D prefix sums dla sum podmacrzy, prefix XOR i difference arrays dla aktualizacji zakresów. Jeśli tablica zmienia się często, użyj zamiast tego drzewa Fenwick/segment. Uważaj na przesunięcie indeksu (rozmiar n+1).

## Dlaczego to ważne

Sumy prefiksowe zamieniają powtarzające się O(n) zapytania na zakresy w O(1) wyszukiwania — ogromna wygrana, gdy zapytania są częste.

Wzorzec wstępnego obliczenia raz i szybkiej odpowiedzi uogólnia się na wiele zadań przetwarzania danych.

To jest podstawowy element programowania konkurencyjnego i powszechny element konstrukcyjny w analityce.