Easy Prefix Sum Arrays & Strings
In plain English: Pre-process an array so you can instantly answer 'what is the sum between index l and r?'
Prefix sums turn any range-sum query into a subtraction of two precomputed values — trade O(n) setup for O(1) per query.
Prompt
Given array a, answer multiple range-sum queries [l, r] efficiently.
Try to write it from scratch before scrolling down.
Solution
def build_prefix(a):
p = [0] * (len(a) + 1)
for i in range(len(a)):
p[i + 1] = p[i] + a[i] # p[i] = sum of a[0..i-1]
return p
def range_sum(p, l, r):
return p[r + 1] - p[l]
# a = [1,3,5,7,9]; p = build_prefix(a)
# range_sum(p, 1, 3) == 15 (3+5+7)