Ein Prefix Sum Array speichert kumulierte Summen, sodass beliebige Range Sum Anfragen nach O(n) Vorverarbeitung in O(1) beantwortet werden können — statt O(n) pro Abfrage.
Die Idee
Sei die Summe der ersten Elemente. Dann ist die Summe von gleich .
Ein Prefix Sum Array speichert kumulierte Summen, sodass beliebige Range Sum Anfragen nach O(n) Vorverarbeitung in O(1) beantwortet werden können — statt O(n) pro Abfrage.
Sei die Summe der ersten Elemente. Dann ist die Summe von gleich .
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 viele Range-Sum-Anfragen auf statischen Daten. Varianten: 2D Prefix Sums für Submatrix-Summen, Prefix XOR und Difference Arrays für Range-Updates. Falls das Array sich häufig ändert, nutzen Sie stattdessen einen Fenwick/Segment Tree. Achten Sie auf Index-Offset (Größe n+1).
Prefix Sums verwandeln wiederholte O(n) Range Queries in O(1) Lookups — ein enormer Gewinn, wenn Abfragen häufig sind.
Das Muster "einmal vorberechnen, schnell antworten" verallgemeinert sich auf viele Datenverarbeitungsaufgaben.
Es ist ein Grundpfeiler der Wettbewerbsprogrammierung und ein häufiger Baustein in der Datenanalyse.