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 ya kasance jimlat na farko abubuwa. Sai jimlat na ita ce .
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.
Bari ya kasance jimlat na farko abubuwa. Sai jimlat na ita ce .
prefix[i]iarr[l..r]prefix[r+1] - prefix[l]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
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
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).
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.