Een prefix sum array slaat cumulatieve totalen op, zodat elke range sum in O(1) kan worden beantwoord na O(n) voorbereiding — in plaats van O(n) per query.
Het idee
Laat de som van de eerste elementen zijn. Dan is de som van gelijk aan .
Een prefix sum array slaat cumulatieve totalen op, zodat elke range sum in O(1) kan worden beantwoord na O(n) voorbereiding — in plaats van O(n) per query.
Laat de som van de eerste elementen zijn. Dan is de som van gelijk aan .
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
Ideaal voor veel range-sum queries op statische gegevens. Varianten: 2D prefix sums voor submatrix sums, prefix XOR en difference arrays voor range updates. Als de array vaak verandert, gebruik in plaats daarvan een Fenwick/segment tree. Let op de index offset (grootte n+1).
Prefix sums veranderen herhaalde O(n) range queries in O(1) lookups — een enorme winst wanneer queries frequent zijn.
Het patroon van eenmaal voorberekenen, snel antwoorden generaliseert naar veel data-verwerkingstaken.
Het is een basiselement van competitief programmeren en een veelgebruikt bouwblok in analytics.