Prefix Sum Technique Explained
Prefix Sum
A prefix sum transforms an array into a new array of running totals. For an input array arr, define prefix[k] as the sum of all elements before index k: prefix[0] = 0, prefix[1] = arr[0], prefix[2] = arr[0] + arr[1], and so on.
The power of this transformation is that any subarray sum reduces to a single subtraction. To find the sum of arr[i:j], you compute prefix[j] - prefix[i]. Without prefix sums, summing that range requires looping through each element. With them, it takes constant time regardless of range length.
Building the prefix array costs O(n) time and O(n) space, but every subsequent range query runs in O(1). This trade-off is worthwhile whenever the same array is queried many times, or when you need to search over all possible subarray boundaries efficiently.
The following problem illustrates a canonical use of this technique: instead of testing every possible subarray, the prefix sum turns the search into a hash table lookup.
Given an integer array arr and a target value, return a subarray whose sum equals the target. Return the answer as [start, end), where start is inclusive and end is exclusive. If there are multiple valid answers, return the one with the smaller end value.
Input: arr = [1, -20, -3, 30, 5, 4], target = 7
Output: [1, 4]
The subarray arr[1:4] = [-20, -3, 30] sums to 7.