Nambari ya jumla ya awali inaboresha jumla ya cumulative ili jumla ya eneo lolote ijaweze kujibu kwa O(1) baada ya usindikaji wa O(n) — badala ya O(n) kwa kila swali.
Wazo
Ikini kuwa jumla ya elementi za za kwanza. Kisha jumla ya ni .
Nambari ya jumla ya awali inaboresha jumla ya cumulative ili jumla ya eneo lolote ijaweze kujibu kwa O(1) baada ya usindikaji wa O(n) — badala ya O(n) kwa kila swali.
Ikini kuwa jumla ya elementi za za kwanza. Kisha jumla ya ni .
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
Inahitajika kwa maswali mengi ya jumla ya eneo kwa data tuli. Tofauti: jumla ya awali ya 2D kwa jumla ya submatrix, XOR ya awali na safu za tofauti kwa sasisho la eneo. Ikiwa nambari inabadilika mara kwa mara, tumia mti wa Fenwick/segment badala yake. Jinga offset ya index (ukubwa n+1).
Jumla ya awali inabadilisha maswali ya eneo ya O(n) yanayorudiwa kuwa utaftaji wa O(1) — ushindi mkubwa wakati maswali yanakuwa ya kawaida.
Mtindo wa kuhesabu-mara-moja-na-kujibu-haraka unajumlisha kazi nyingi za usindikaji wa data.
Ni sehemu ya kawaida ya programu ya ushindani na kijenzi cha kawaida katika uchambuzi.
Maktaba ya maswali ya mahojiano ya IT yenye majibu ya kina — kutoka Junior hadi Senior.
Changia