Precompute running totals so any range query collapses to one subtraction.
What the prefix sums pattern is
A prefix sum array stores, at each position i, the total of everything before it: prefix[i] = a[0] + ... + a[i-1], with prefix[0] = 0. Once built in one O(n) pass, the sum of any range [l, r] is prefix[r+1] - prefix[l] - a subtraction instead of a loop. Many queries over static data amortize beautifully: O(n) preprocessing, O(1) per query.
The deeper trick is pairing prefix sums with a hash map. 'Sum of subarray ending at r equals k' rewrites to 'prefix[r+1] - k appeared as an earlier prefix'. Counting subarrays with a property becomes counting earlier prefix values - one pass, one map.
How to recognize it
Signals: repeated range-sum queries, 'count subarrays whose sum equals / is divisible by k', running balances (treat one symbol as +1 and another as -1), or 2D block sums. The idea generalizes beyond sums to anything invertible: prefix XOR works identically because XOR is its own inverse; prefix products work when zeros are handled separately.
Crucially, this is the pattern that survives negative numbers. A sliding window needs monotonic growth to justify shrinking; negatives break that. Prefix + hash map does not care about sign - which is why 'subarray sum equals k with negatives allowed' is prefix-sums, not sliding-window.
The prefix + hash map template
Walk the array once, maintaining the running sum. At each element, ask: how many earlier prefixes equal (current sum - k)? Each such prefix marks a start point of a subarray summing to k. Then record the current prefix in the map. Seeding the map with {0: 1} counts subarrays that start at index 0 - forgetting that seed is the pattern's most common bug.
pseudocode
count = 0; sum = 0
seen = {0: 1} # empty prefix - do not forget
for x in a:
sum += x
count += seen.get(sum - k, 0)
seen[sum] = seen.get(sum, 0) + 1
return count
Complexity
Build: O(n) time, O(n) space. Range query: O(1). The hash-map variants stay one pass, O(n) time and up to O(n) map entries. 2D prefix sums build in O(rows x cols) and answer any rectangle sum with four lookups via inclusion-exclusion.
Common pitfalls
Off-by-one in the range formula. With the length-(n+1) convention, sum of [l, r] inclusive is prefix[r+1] - prefix[l]. Write the convention as a comment before using it.
Missing the {0: 1} seed, silently dropping every subarray that starts at index 0.
Updating the map before querying it - a subarray of length zero 'matches itself' when k is 0. Query first, then record.
For divisibility problems, normalize negative remainders (in languages where % can be negative) before using them as map keys.
Reaching for a sliding window when the array has negatives - the window's shrink logic is unsound there; prefix sums are the correct tool.
Worked examples
1. Subarray sum equals Kmedium
Given an integer array (positives and negatives) and an integer k, count the subarrays whose elements sum to exactly k.
Negatives rule out a sliding window: growing the window doesn't monotonically grow the sum, so shrink decisions mean nothing.
Rewrite: subarray (l, r] sums to k exactly when prefix[r] - prefix[l] = k, i.e. an earlier prefix equals current - k.
One pass with a running sum and a map of prefix-value -> occurrences; at each step add seen[sum - k] to the count, then record sum.
Seed with {0: 1} so subarrays starting at index 0 are counted. O(n) time, O(n) space.
pseudocode
count = 0; sum = 0; seen = {0: 1}
for x in nums:
sum += x
count += seen.get(sum - k, 0)
seen[sum] = seen.get(sum, 0) + 1
return count
Remember: 'Some subarray sums to k' is 'two prefixes differ by k' - and pair-counting with a hash map is one pass.
2. Product of array except selfmedium
Return an array where output[i] is the product of every element except nums[i], without using division and in O(n).
output[i] is (product of everything left of i) x (product of everything right of i) - a prefix pass and a suffix pass.
First pass left-to-right: write the running prefix product into output before multiplying in the current element.
Second pass right-to-left: carry a running suffix product, multiplying it into output[i] before extending it - reusing the output array keeps extra space O(1).
Two passes, no division, and zeros need no special casing because nothing is ever divided.
pseudocode
output = [1] * n
left = 1
for i in 0 .. n-1:
output[i] = left
left *= nums[i]
right = 1
for i in n-1 .. 0:
output[i] *= right
right *= nums[i]
return output
Remember: 'Everything except me' = prefix from the left times suffix from the right - two sweeps that never need division.
3. Contiguous array (equal 0s and 1s)medium
Given a binary array, find the length of the longest contiguous subarray containing an equal number of 0s and 1s.
Recode 0 as -1. Now 'equal 0s and 1s' means 'subarray sum is zero' - a running balance problem.
A zero-sum subarray (l, r] exists exactly when prefix[l] == prefix[r]: the balance returned to a value seen before.
For longest length, the map stores each balance's first index; on repeat, candidate length is current index minus stored index.
Seed balance 0 at index -1 to handle subarrays starting at 0. One pass, O(n). The recode-to-plus-minus-one move transfers to many 'equal counts' problems.
pseudocode
first = {0: -1}; balance = 0; best = 0
for i in 0 .. n-1:
balance += (nums[i] == 1 ? 1 : -1)
if balance in first:
best = max(best, i - first[balance])
else:
first[balance] = i
return best
Remember: Recode categories as +1/-1 and 'equal counts' becomes 'balance repeats' - a prefix value seen twice brackets the answer.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1With prefix[0] = 0, what is the sum of elements from index l to r inclusive?
prefix[r] - prefix[l]
✓ prefix[r+1] - prefix[l]
prefix[r] - prefix[l-1] + a[l]
prefix[r+1] - prefix[l+1]
prefix[r+1] totals a[0..r] and prefix[l] totals a[0..l-1]; their difference is exactly a[l..r]. Fixing this convention up front prevents the pattern's classic off-by-one.
2In the prefix + hash map counting template, what does seeding the map with {0: 1} accomplish?
It handles empty input arrays
✓ It counts subarrays that begin at index 0, whose 'earlier prefix' is the empty prefix
It prevents division by zero
It makes the map non-empty for the first lookup
A subarray starting at index 0 with sum k satisfies prefix[r] - 0 = k; the 0 is the empty prefix. Without the seed, all such subarrays are silently dropped.
3Why is 'count subarrays with sum k' solved with prefix sums rather than a sliding window when the array has negatives?
Prefix sums are faster than sliding windows
✓ Negatives break the monotonicity that justifies window shrinking, while prefix differences remain valid for any signs
Sliding windows cannot count, only measure length
It isn't - a sliding window works fine
The window shrink step assumes growing the window grows the sum. Negatives void that assumption; prefix[r] - prefix[l] = k is sign-agnostic algebra.
4How does the 'longest subarray with equal 0s and 1s' problem become a prefix-sum problem?
By sorting the array first
✓ By recoding 0 as -1, so equal counts become a zero-sum subarray, i.e. a repeated running balance
By counting zeros and ones separately with two maps
By using XOR instead of sum
After the recode, equal 0s/1s means the balance is unchanged across the range - the same prefix value at both ends. Storing each balance's first index yields the longest such range.
Frequently asked questions
When do prefix sums beat a sliding window?
Whenever elements can be negative, whenever you must count occurrences rather than optimize a window length over positives, and whenever many range queries hit static data. Windows win when monotonic grow/shrink logic applies - typically all-positive values.
Do prefix techniques work for operations other than addition?
Yes, for any invertible operation: prefix XOR is the direct analogue (XOR is self-inverse), and prefix products work with separate zero handling. Min and max do not invert, so they need different tools (sparse tables, monotonic deques).
What changes in two dimensions?
Build P[i][j] = sum of the rectangle from the origin to (i-1, j-1) via inclusion-exclusion, then any rectangle sum is four lookups: P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]. Same idea, one more dimension of off-by-one care.