Prefix sums

A prefix sum is a precomputed list of running totals: entry i holds the sum of everything before position i. Once you have it, the sum of any range is just one total minus another, like reading two odometer values to get the distance of one leg of a trip. Building it takes one pass; every range query after that is instant instead of a fresh loop. The same idea extends to 2D grids, where you can get the sum of any rectangle from four lookups, and to counting, where you store running counts instead of sums. It’s a small trick that shows up constantly in interview problems involving subarrays.