Menene jimlat ragowar kuma ta ta hanzari abubuwan tambajin jeri?

Question

Accepted Answer

Jerin **jimlat ragowar** yana adana jimlar jummowa don haka kowane **jimlat jeri** zai iya amsa a cikin **O(1)** bayan juyawa O(n) — maimakon O(n) bisa ga istaefon.

## Tunanin

Bari `prefix[i]` ya kasance jimlat na farko `i` abubuwa. Sai jimlat na `arr[l..r]` ita ce `prefix[r+1] - prefix[l]`.

## Misali

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

## Trace

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

## Rikitarwa

- **Gina:** O(n). **Tambaja:** O(1). **Sararin:** O(n).

## Yaushe za mu yi amfani da / Damina

Dai idẻal ne don **yawa tambajin jimlat-jeri** akan bayanan da ba sa juyawa. Sauran nau'i: jimlat ragowar 2D don jimlat karamar matrix, jimlat ragowar XOR, da kuma sanarwa na bambanci don saumarwa jeri. Idan jerin ya canja akai-akai, yi amfani da itacen Fenwick/segment maimakon haka. Kula da offset na saurau (girman n+1).

## Me yasa ake daurare

Jimlat ragowar suna juyar da jimlat jeri O(n) na maimaita zuwa neman O(1) — baba babbar nasara lokacin da tambajin za su kasance akai-akai.

Alaka na gajeriyar jiyya-ɗaya, amsa da sauri yana bade ga hanyar sarrar abubuwa masu yawa.

Ita shine abin mahimman gida na kolokwel gida kuma abin saniyan kariya mai karfi a analisa.