Apa iku prefix sum, lan kepriye cara nyepat range queries?

Question

IT Interview Practice · Accepted Answer

Array **prefix sum** nyimpen total kumulatif supaya bisa menjawab **range sum** apa wae ing **O(1)** sawise preprocessing O(n) — ora O(n) per query.

## Ideya

Misale `prefix[i]` iku sum saka `i` elemen pisanan. Banjur sum saka `arr[l..r]` iku `prefix[r+1] - prefix[l]`.

## Conto

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

## Trace

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

## Kompleksitas

- **Bangun:** O(n). **Query:** O(1). **Ruang:** O(n).

## Kapan digunakan / jebakan

Ideal untuk **query range-sum akeh** ing data statik. Varyan: prefix sums 2D kanggo submatrix sums, prefix XOR, lan difference arrays kanggo range updates. Yen array sering owah, gunaake Fenwick/segment tree. Ati-ati offset indeks (ukuran n+1).

## Kepriye carane penting

Prefix sums ngowahi range queries O(n) berulang dadi O(1) lookups — menang gedhe banget yen queries asring.

Pola precompute-sekali, jawab-cepet umum kanggo akeh tugas pengolahan data.

Iku elemen pokok competitive programming lan blok pembangun umum ing analitik.

Ideya

Conto

Trace

Kompleksitas

Kapan digunakan / jebakan

Kepriye carane penting

Pitakon sing gegandhengan