Prefix Sums Pattern
A prefix-sum array stores cumulative totals so any range sum is a single subtraction. Combined with a hash map, it turns 'subarray summing to k' into a linear-time lookup.
Typical complexity: O(n) preprocessing, O(1) per query
When to use it
- You answer many range-sum or range-count queries.
- You're counting subarrays with a target sum.
- The array is static and queries dominate.
Practice problems
Read the approach or generate an interactive, step-by-step lesson:
Deep dive
Prefix Sums Pattern: The Simplest Way to Answer Range Queries Fast
Learn how prefix sums turn repeated range calculations from linear work into constant-time queries, and see how the pattern extends to hash maps and subarray problems.
Master prefix sums by doing
codebrew.ai turns each problem into an interactive lesson — trace the algorithm variable by variable until the pattern clicks.
Start a free lesson