Un array de prefix sum stochează totaluri cumulative, astfel încât orice range sum poate fi răspuns în O(1) după O(n) preprocessing — în loc de O(n) pe interogare.
Ideea
Fie suma primelor elemente. Atunci suma lui este .
Un array de prefix sum stochează totaluri cumulative, astfel încât orice range sum poate fi răspuns în O(1) după O(n) preprocessing — în loc de O(n) pe interogare.
Fie suma primelor elemente. Atunci suma lui este .
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 pentru multe interogări range-sum pe date statice. Variante: sume de prefix 2D pentru sume de submatrici, XOR de prefix și difference arrays pentru actualizări de interval. Dacă array-ul se schimbă frecvent, folosește în schimb un arbore Fenwick/segment. Atenție la decalajul indexului (dimensiune n+1).
Sumele de prefix transformă interogările de interval O(n) repetate în căutări O(1) — o câștig imens când interogările sunt frecvente.
Patternul de pre-calcul o dată, răspuns rapid se generalizează la multe sarcini de prelucrare a datelor.
Este un element esențial al programării competitive și un bloc de construcție comun în analiză.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează