Çfarë është një shumë parashtese dhe si e përshpejton atë poizitat e diapazonit?

Question

Accepted Answer

Një niz **shumë parashtese** ruan totalet kumulative kështu që çdo **shumë diapazoni** mund t'u përgjigjet në **O(1)** pas përpunimit O(n) — në vend të O(n) për pyetje.

## Ideja

Le të jetë `prefix[i]` shuma e `i` elementeve të parë. Atëherë shuma e `arr[l..r]` është `prefix[r+1] - prefix[l]`.

## Shembull

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

## Ślad

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

## Kompleksiteti

- **Ndërtim:** O(n). **Pyetje:** O(1). **Hapësirë:** O(n).

## Kur të përdoret / Grackat

Ideale për **shumë pyetje për shumën e diapazonit** në të dhëna statike. Variante: shuma parashtese 2D për shuma nënmatrice, XOR parashtese dhe vargje diference për përditësime diapazoni. Nëse vargu ndryshon shpesh, përdorni një pemë Fenwick/segment në vend të kësaj. Kini kujdes ndaj kompensimit të indeksit (madhësia n+1).

## Pse është e rëndësishme

Shumat parashtese kthejnë pyetje të përsëritura O(n) në kërkime O(1) — një fitim i madh kur pyetjet janë të shpeshta.

Shenia e llogaritjes njëherë dhe përgjigjes shpejt përgjithësohet në shumë detyra përpunimi të dhënash.

It is a staple of competitive programming and a common building block in analytics.