Un array di somma di prefissi memorizza totali cumulativi in modo che qualsiasi somma di intervallo possa essere risolta in O(1) dopo un preprocessamento O(n) — invece di O(n) per query.
L'idea
Sia la somma dei primi elementi. Allora la somma di è .
Un array di somma di prefissi memorizza totali cumulativi in modo che qualsiasi somma di intervallo possa essere risolta in O(1) dopo un preprocessamento O(n) — invece di O(n) per query.
Sia la somma dei primi elementi. Allora la somma di è .
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
Ideale per molte query di somma su intervalli su dati statici. Varianti: somme di prefissi 2D per somme di sottomatrici, XOR di prefissi e array di differenze per aggiornamenti di intervalli. Se l'array cambia spesso, usa un albero Fenwick/segment invece. Attenzione all'offset dell'indice (dimensione n+1).
Le somme di prefissi trasformano query di intervallo ripetute O(n) in ricerche O(1) — un enorme vantaggio quando le query sono frequenti.
Il pattern precalcola una volta, rispondi velocemente si generalizza a molti compiti di elaborazione dati.
È un elemento fondamentale della programmazione competitiva e un blocco costitutivo comune nell'analittica.
Una raccolta di domande di colloquio IT con risposte dettagliate — da Junior a Senior.
Dona