Prefix sums

What it is

A prefix sum array stores, at each index, the running total of everything up to that point. Once you have it, the sum of any subarray is one subtraction away (prefix[j] - prefix[i]) instead of a fresh scan. The technique's reach goes well beyond literal sums: a lot of "count subarrays with property X" questions become prefix-sum questions once you find the right transformation — turning 0/1 into -1/1 to talk about balance, or reducing to "does a subarray sum to a multiple of k" via remainders. Paired with a hash map of prefix values seen so far, it turns an O(n²) subarray-counting scan into O(n).

When it applies

• You need the sum (or count, or balance) of many different subarrays or ranges, and the underlying array does not change between queries — that "static, many queries" shape is exactly what a precomputed prefix buys you.
• The question is "how many subarrays satisfy X" where X can be restated as a target sum or a target remainder over a transformed array.
• If the array is mutated between queries (a "point update" alongside range queries), a plain prefix sum breaks — that calls for a Fenwick tree or segment tree, not this pattern in its basic form.
• If you're choosing which subarray to keep under a size or content constraint (not counting or summing), you're more likely in sliding-window territory than prefix-sum territory.

Tells in the problem

• "Answer many sumRange queries" against an array that is built once and never modified afterward.
• "Count the subarrays" whose sum equals, or is a multiple of, some target value.
• A binary or two-valued array where the actual ask is really about balance or a difference in counts (equal 0s and 1s, exactly k odds) — a hint to map values to +1/-1 or 1/0 first.
• Divisibility language ("sum is a multiple of k") on a sum-of-subarray question — a hint to compare prefix sums by their remainder mod k, not their raw value.
• A weighted-random-pick or "which bucket does this point land in" design, where cumulative weights plus a binary search stand in for prefix sums over probabilities.

The classic mistake

The failure interviewers report most is computing the running sum correctly but then re-deriving each subarray sum with a fresh inner loop anyway — effectively building the prefix array and never using it, which quietly leaves the solution at O(n²). This happens because the insight "sum(i..j) = prefix[j] - prefix[i-1]" is easy to state but easy to forget to actually apply once the code is mid-write, especially once a hash map or an off-by-one on the prefix index enters the picture. The second, more subtle version of this mistake is getting the prefix's off-by-one wrong when counting subarrays with a hash map — forgetting to seed the map with {0: 1} for the empty prefix, which silently drops every subarray that starts at index 0.

Questions to start with

• Range Sum Query - Immutable — the direct, no-tricks case: build the prefix array once, answer every query with one subtraction.
• Subarray Sum Equals K — introduces the hash-map-of-prefix-sums trick for counting subarrays, including the {0: 1} seed for subarrays starting at index 0.
• Contiguous Array — shows the value-transform step: mapping 0/1 to -1/1 turns a balance question into a "sum equals zero" question.
• Continuous Subarray Sum — moves from raw prefix values to prefix sums modulo k, for a divisibility condition.
• Random Pick with Weight — the pattern applied outside pure summation: cumulative weights plus binary search to sample proportionally.