Co je prefix sum a jak zrychluje range queries?

Question

IT Interview Practice · Accepted Answer

Pole **prefix sum** uchovává kumulativní součty, aby bylo možné odpovědět na jakýkoli **range sum** v **O(1)** po O(n) předzpracování — místo O(n) na dotaz.

## Myšlenka

Nechť `prefix[i]` je součet prvních `i` prvků. Potom součet `arr[l..r]` je `prefix[r+1] - prefix[l]`.

## Příklad

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

## Trasování

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

## Složitost

- **Výstavba:** O(n). **Dotaz:** O(1). **Prostor:** O(n).

## Kdy použít / Úskalí

Ideální pro **mnoho range-sum dotazů** na statických datech. Variace: 2D prefix sums pro součty submatic, prefix XOR a difference arrays pro aktualizace rozsahů. Pokud se pole často mění, místo toho použijte Fenwick/segment tree. Pozor na offset indexu (velikost n+1).

## Proč na tom záleží

Prefix sums mění opakované O(n) range queries na O(1) vyhledávání — obrovský zisk, když jsou dotazy časté.

Vzor jednoho předzpracování a rychlé odpovědi se zobecňuje na mnoho úloh zpracování dat.

Je to nezbytná součást konkurenčního programování a běžný stavební blok v analýze.

Myšlenka

Příklad

Trasování

Složitost

Kdy použít / Úskalí

Proč na tom záleží

Související otázky