Prefix Sum

You are handed an array and asked, over and over, for the sum of a range: elements 2 through 5, then 0 through 3, then 4 through 7. The obvious approach adds up each range when asked. That is fine for one query, but if you have thousands of queries you re-add the same numbers endlessly, and the cost balloons.

A prefix sum fixes this by doing the adding once, up front. You build an array where each slot holds the running total up to that point. After that, the sum of any range is a single subtraction of two precomputed totals, in constant time. The same idea, cumulative totals you can difference, unlocks a surprising trick: paired with a hash map, prefix sums can count how many subarrays add up to a target, in one pass.

This unit builds the prefix sum array, shows why the range subtraction works, and then connects it to the hash map for the problems that make prefix sum click. It is one of the highest-return techniques for the effort it takes to learn.