Jumla ya awali ni nini, na inaharakisha vipi maswali ya eneo?

Question

Accepted Answer

Nambari ya **jumla ya awali** inaboresha jumla ya cumulative ili **jumla ya eneo** lolote ijaweze kujibu kwa **O(1)** baada ya usindikaji wa O(n) — badala ya O(n) kwa kila swali.

## Wazo

Ikini `prefix[i]` kuwa jumla ya elementi za `i` za kwanza. Kisha jumla ya `arr[l..r]` ni `prefix[r+1] - prefix[l]`.

## Mfano

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

## Kufuatilia

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

## Ugumu

- **Kujenga:** O(n). **Swali:** O(1). **Nafasi:** O(n).

## Wakati wa kutumia / Mitego

Inahitajika kwa **maswali mengi ya jumla ya eneo** kwa data tuli. Tofauti: jumla ya awali ya 2D kwa jumla ya submatrix, XOR ya awali na safu za tofauti kwa sasisho la eneo. Ikiwa nambari inabadilika mara kwa mara, tumia mti wa Fenwick/segment badala yake. Jinga offset ya index (ukubwa n+1).

## Kwa nini inastahili

Jumla ya awali inabadilisha maswali ya eneo ya O(n) yanayorudiwa kuwa utaftaji wa O(1) — ushindi mkubwa wakati maswali yanakuwa ya kawaida.

Mtindo wa kuhesabu-mara-moja-na-kujibu-haraka unajumlisha kazi nyingi za usindikaji wa data.

Ni sehemu ya kawaida ya programu ya ushindani na kijenzi cha kawaida katika uchambuzi.