Cad is suim réimír ann, agus conas a bhraistear ar dhochtuimh raon a thrasú?

Question

Accepted Answer

Stóraíonn eagar **suim réimír** iomlán dhíreach chun go bhféadfaí aon **suim raon** a fhreagairt in **O(1)** tar éis réamhpróiseála O(n) — in ionad O(n) in aghaidh an iarratas.

## An smaoineamh

Bíodh `prefix[i]` mar shuim an chéad `i` eilimint. Ansin is ionann suim `arr[l..r]` agus `prefix[r+1] - prefix[l]`.

## Sampla

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

## Rian

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

## Castacht

- **Tógáil:** O(n). **Iarratas:** O(1). **Spás:** O(n).

## Cathain a úsáid / gabháltas

Ideálach do **go leor iarratas suim raon** ar shonraí statach. Athruithe: suimeanna réimír 2D do shuimeanna fomhaitrís, réimír XOR, agus eagair dhifríochta do nuashonruithe raon. Má tá an eagar ag athrú go minic, bain úsáid as crann Fenwick/segment in ionad sin. Bí faichilleach faoin bhfoluain innéacs (méid n+1).

## Cad is fiúntach

Iompraíonn suimeanna réimír iarratas raon O(n) athraitheach ina cuardach O(1) — buaicphointe mór nuair a bhíonn iarratas iomaíoch ann.

Géineáiltíonn an patrún réamhríomh-aon-uair, fregra-gasta go leor tasc próiseála sonraí.

Is gné bhunúsach de dhréimpleogacht iomaíoch agus bloc tógála coitianta in anailís í.