Prefix Sums

If you've ever been asked "what's the sum of elements between index i and j?" more than once on the same array, recomputing that sum by walking the subarray every time is wasteful. If the array has n elements and you get q queries, that's O(n*q) work in the worst case. Prefix sums fix this by doing a single O(n) pass up front so that every future range query costs O(1).

The core idea

A prefix-sum array prefix stores running totals: prefix[i] is the sum of all elements from the start of the array up to (but not including) index i. It's common to build this array with a leading sentinel 0, so prefix[0] = 0 and prefix[i] = prefix[i-1] + nums[i-1]. That sentinel is what makes range queries clean: it represents "the sum of zero elements," and it lets prefix[j+1] - prefix[i] compute the sum of nums[i..j] inclusive, without special-casing i = 0.

Once prefix is built, any inclusive range sum rangeSum(i, j) = prefix[j+1] - prefix[i] is a single subtraction. The preprocessing costs O(n) time and O(n) extra space; every query after that costs O(1) time. This is the classic "pay once, query forever" trade-off, and it shows up constantly in interviews whenever an array is static (not being updated between queries) and you need to answer many range-sum-style questions.

Counting subarrays with a target sum

A powerful extension combines prefix sums with a hash map. Suppose you want to count how many contiguous subarrays sum to exactly k. Walking every subarray is O(n^2). Instead, notice that if prefix[j+1] - prefix[i] = k, then a subarray ending at index j sums to k whenever some earlier prefix value equals prefix[j+1] - k. So as you scan left to right building the running sum, you keep a hash map of how many times each prefix-sum value has been seen so far. At each step, you look up runningSum - k in the map to see how many earlier positions would complete a valid subarray, add that count to your answer, then record the current running sum in the map. This turns an O(n^2) brute force into a single O(n) pass, at the cost of O(n) extra space for the map. The trick of seeding the map with {0: 1} before scanning handles the case where a prefix subarray starting at index 0 itself sums to k.