PrefixPrefix Techniques
Prefix Sum
Precompute P[i] = a[0] + … + a[i-1] once so that any subarray sum a[l..r] is P[r+1] − P[l] in O(1).
a
3
0
1
1
4
2
1
3
5
4
9
5
2
6
6
7
P (prefix sums)
0
0
1/13Build P where P[i] is the sum of the first i elements. P[0] = 0 (empty prefix) so every query has a clean left endpoint.
Being addedQueried rangePrefix entries usedAnswer
PseudocodeLearn Prefix Sum →
1P[0] = 02for i in 0 .. n-1: P[i+1] = P[i] + a[i]3query(l, r) = P[r+1] - P[l]Variables
n8
Complexity
best O(n)
avg O(n)
worst O(n)
space O(n)
Speed