The Prefix Sum Pattern
Precompute cumulative totals once, then answer any range-sum query as the difference of two prefix values. Pairing prefix sums with a hash map turns "count subarrays summing to k" into a single pass.
3
Interactive problems1
Free to openHow to recognise a prefix sum problem
The problem asks about sums or counts over many subarrays or ranges, especially with repeated queries over unchanging data. "Subarray sum equals k" and "range sum query" are the standard forms.
Time and space complexity
O(n) preprocessing, then O(1) per range query — against O(n) per query when summing directly.
Prefix Sum practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Related patterns and concepts
The underlying technique is covered from first principles in the prefix sum lesson in the DSA visualizer curriculum. Prefix Sum is one of the 16 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.