X'inhu l-prefix sum, u kif jħaffef il-range queries?

Question

Accepted Answer

Array **prefix sum** jaħżen somom kummulativi sabiex kwalunkwe **range sum** jista' jiġi miegħed f'**O(1)** wara l-preprocessing O(n) — minflok O(n) kull query.

## L-idea

Halli `prefix[i]` tkun is-suma tal-ewwel `i` elementi. Allura s-suma ta' `arr[l..r]` hija `prefix[r+1] - prefix[l]`.

## Eżempju

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

## Traċċa

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

## Kumplessità

- **Ibni:** O(n). **Query:** O(1). **Spazju:** O(n).

## Meta tuża / pitragunak

Ideali għal **ħafna range-sum queries** fuq data statika. Varjanti: prefix sums 2D għal submatrix sums, prefix XOR, u difference arrays għal range updates. Jekk l-array jinbidel spiss, uża Fenwick/segment tree minflok. Agħti attenzjoni għall-offset ta' l-indiċi (daqs n+1).

## Għaliex huwa importanti

Il-prefix sums jibdlu r-repeated O(n) range queries f'O(1) lookups — rebbieħa kbira meta queries huma frewenti.

Il-precompute-darba, meet-harġa pattern jiġeneralizza għal bosta data-processing tasks.

Hu element fundamentali ta' competitive programming u common building block fl-analytics.