En prefix sum matrise lagrer kumulative totaler slik at ethvert range sum kan besvares i O(1) etter O(n) forbehandling — i stedet for O(n) per spørring.
Idéen
La være summen av de første elementene. Da er summen av lik .
En prefix sum matrise lagrer kumulative totaler slik at ethvert range sum kan besvares i O(1) etter O(n) forbehandling — i stedet for O(n) per spørring.
La være summen av de første elementene. Da er summen av lik .
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
Ideell for mange range-sum spørringer på statiske data. Varianter: 2D prefix sums for submatrix sums, prefix XOR og difference arrays for range updates. Hvis matrisen endres ofte, bruk i stedet Fenwick/segment tree. Se opp for indeksoffset (størrelse n+1).
Prefix sums gjør gjentatte O(n) range spørringer til O(1) oppslag — en stor seier når spørringer er hyppige.
Mønsteret med å forberegne en gang og svare raskt generaliseres til mange databehandlingsoppgaver.
Det er et grunnleggende element i konkurranseprogrammering og en vanlig byggestein i analyser.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner