Un tableau de somme de préfixe stocke les totaux cumulatifs afin que toute somme de plage puisse être répondue en O(1) après un prétraitement O(n) — au lieu de O(n) par requête.
L'idée
Soit la somme des premiers éléments. Alors la somme de est .
Un tableau de somme de préfixe stocke les totaux cumulatifs afin que toute somme de plage puisse être répondue en O(1) après un prétraitement O(n) — au lieu de O(n) par requête.
Soit la somme des premiers éléments. Alors la somme de est .
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
Idéale pour nombreuses requêtes de somme de plage sur données statiques. Variantes : sommes de préfixe 2D pour sommes de sous-matrice, XOR de préfixe, et tableaux de différence pour mises à jour de plage. Si le tableau change souvent, utilisez plutôt un arbre de Fenwick/segment. Attention au décalage d'index (taille n+1).
Les sommes de préfixe transforment des requêtes de plage O(n) répétées en des recherches O(1) — un énorme gain lorsque les requêtes sont fréquentes.
Le modèle précontrôler une fois, répondre rapidement se généralise à de nombreuses tâches de traitement de données.
C'est un élément essentiel de la programmation compétitive et un bloc de construction courant en analyse.