Apakah itu jumlah awalan, dan bagaimana ia mempercepat pertanyaan rentang?

Question

Accepted Answer

Array **jumlah awalan** menyimpan jumlah kumulatif sehingga **jumlah rentang** apa pun dapat dijawab dalam **O(1)** setelah preprocessing O(n) — bukannya O(n) per pertanyaan.

## Idenya

Biarkan `prefix[i]` menjadi jumlah elemen `i` pertama. Maka jumlah `arr[l..r]` adalah `prefix[r+1] - prefix[l]`.

## Contoh

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

## Jejak

```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). **Pertanyaan:** O(1). **Ruang:** O(n).

## Kapan digunakan / jebakan

Ideal untuk **banyak pertanyaan jumlah-rentang** pada data statis. Varian: jumlah awalan 2D untuk jumlah submatriks, awalan XOR, dan larik perbedaan untuk pembaruan rentang. Jika array sering berubah, gunakan pohon Fenwick/segment. Perhatikan offset indeks (ukuran n+1).

## Mengapa hal ini penting

Jumlah awalan mengubah pertanyaan rentang O(n) berulang menjadi pencarian O(1) — kemenangan besar saat pertanyaan sering.

Pola pra-hitung sekali, jawab-cepat menggeneralisasi untuk banyak tugas pemrosesan data.

Ini adalah elemen penting pemrograman kompetitif dan blok bangunan umum dalam analitik.