Što je prefiksna suma i kako ubrzava upit raspona?

Question

IT Interview Practice · Accepted Answer

Niz **prefiksne sume** pohranjuje kumulativne ukupne vrijednosti tako da se bilo koji **zbir raspona** može odgovoriti u **O(1)** nakon O(n) pretprocesiranja — umjesto O(n) po upitu.

## Ideja

Neka je `prefix[i]` suma prvih `i` elemenata. Tada je suma `arr[l..r]` jednaka `prefix[r+1] - prefix[l]`.

## Primjer

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

## Trag

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

- **Izgradnja:** O(n). **Upit:** O(1). **Prostor:** O(n).

## Kada koristiti / zamke

Idealna za **mnoge upite zbira raspona** na statičkim podacima. Varijante: 2D prefiksne sume za zbir podmatrice, prefiksni XOR i nizovi razlika za ažuriranja raspona. Ako se niz često mijenja, umjesto toga koristite Fenwick/segment stablo. Pazite na pomak indeksa (veličina n+1).

## Zašto je to važno

Prefiksne sume pretvaraju ponavljane O(n) upite raspona u O(1) pretrage — ogromna prednost kada su upiti česti.

Uzorak preračuna jednom, odgovori brzo generalizira se na mnoge zadatke obrade podataka.

To je temelj konkurentnog programiranja i česta sastavnica u analitici.

Ideja

Primjer

Trag

Složenost

Kada koristiti / zamke

Zašto je to važno

Povezana pitanja