#303
Easy
Prefix Sum
Range Sum Query - Immutable
Answer many immutable range-sum queries quickly.
ArrayPrefix Sum
Pattern fit
The whole problem exists to motivate prefix sums: preprocess once, answer each query in O(1).
Key observation
The sum of [l, r] is just prefix[r + 1] - prefix[l].
Target complexity
O(1) query / O(n)
How to break down the solution cleanly
1
The whole problem exists to motivate prefix sums: preprocess once, answer each query in O(1).
2
The sum of [l, r] is just prefix[r + 1] - prefix[l].
3
Define what the cumulative state means.
4
Build the prefix in one forward pass.
Reference implementation
Python# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
Common pitfalls
warning
Off-by-one errors between array indices and prefix indices.
warning
Forgetting the leading zero.
Common follow-ups
How would updates change the data structure choice?
Why is the leading zero worth keeping?
Continue with related problems
Build repeatable depth inside the Prefix Sum cluster before moving on.