En prefiksumma-array lagrar kumulativa totaler så att vilken intervallfråga som helst kan besvaras i O(1) efter O(n) förbehandling — istället för O(n) per fråga.
Idén
Låt vara summan av de första elementen. Då är summan av lika med .
En prefiksumma-array lagrar kumulativa totaler så att vilken intervallfråga som helst kan besvaras i O(1) efter O(n) förbehandling — istället för O(n) per fråga.
Låt vara summan av de första elementen. Då är summan av lika med .
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
Ideal för många intervallfrågor på statisk data. Varianter: 2D-prefiksummor för submatrisummor, prefix XOR och differensarrayer för intervallupdateringar. Om arrayen ändras ofta använder du ett Fenwick/segmentträd istället. Observera indexoffset (storlek n+1).
Prefiksummor förvandlar återstödda O(n) intervallfrågor till O(1) uppslagningar — en stor vinst när frågorna är frekventa.
Mönstret förberäkna-en-gång-och-svar-snabbt generaliseras till många databehandlingsuppgifter.
Det är en grundläggande teknik inom tävlingsprogrammering och en vanlig byggsten inom analys.
Ett bibliotek med IT-intervjufrågor och detaljerade svar — från Junior till Senior.
Donera