The problem partial sums solve
Suppose you have an array of numbers and a list of questions of the form "what is the sum of the elements from index left to index right?". The direct answer is a loop:
const nums: number[] = [3, 1, 4, 1, 5, 9, 2, 6];
let total = 0;
for (let i = 2; i <= 5; i++) {
total += nums[i];
}
console.log(total);
19
One question costs up to n additions. With q questions on an array of n elements, that is O(n * q), which becomes slow when both are large. Partial sums, also called prefix sums, spend O(n) once to prepare, and after that every question takes O(1).
Building the partial sums array
A partial sums array stores, for each position, the sum of everything before it. A convenient layout makes it one element longer than the input: prefix[i] holds the sum of the first i elements, so prefix[0] is 0 (the sum of nothing).
function buildPrefix(nums: number[]): number[] {
const prefix: number[] = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
return prefix;
}
Each entry reuses the one before it, so there is a single pass. For [3, 1, 4, 1, 5, 9, 2, 6] the result is:
[0, 3, 4, 8, 9, 14, 23, 25, 31]
The last entry, 31, is the sum of the whole array.
Answering a range query in O(1)
The sum of the elements from left to right, both included, is everything up to right minus everything before left:
function rangeSum(prefix: number[], left: number, right: number): number {
return prefix[right + 1] - prefix[left];
}
const prefix = buildPrefix([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rangeSum(prefix, 2, 5));
console.log(rangeSum(prefix, 0, 7));
console.log(rangeSum(prefix, 3, 3));
19
31
1
The first call gives prefix[6] - prefix[2], which is 23 - 4 = 19, matching the loop at the top. The extra zero at the front is what makes ranges that start at index 0 work without a special case: prefix[0] is 0, so nothing is subtracted.
Counting with partial sums
The idea isn't limited to adding the values themselves. Add 1 for each element that has a property, and you can count how many elements in any range have it. Here is a count of the letter a in a string:
const word: string = "abracadabra";
const countA: number[] = [0];
for (const ch of word) {
countA.push(countA[countA.length - 1] + (ch === "a" ? 1 : 0));
}
console.log(countA[8] - countA[3]);
3
The result 3 is the number of a characters at indices 3 to 7, in "acada".
Partial sums and the best subarray
A subarray is a contiguous range, and its sum is a difference of two partial sums. So the best subarray ending at a position is the current partial sum minus the smallest partial sum seen before it. Tracking that smallest value while scanning gives a one-pass solution:
function maxViaPrefix(nums: number[]): number {
let best = nums[0];
let minPrefix = 0;
let sum = 0;
for (const v of nums) {
sum += v;
best = Math.max(best, sum - minPrefix);
minPrefix = Math.min(minPrefix, sum);
}
return best;
}
console.log(maxViaPrefix([-2, -5, 6, -2, -3, 1, 5, -6]));
7
This is one way to look at the maximum sum subarray problem in this chapter. It needs only a few variables and not a whole array of partial sums.
Gotchas in TypeScript
- Off-by-one on the right end. With the layout above, the range
left..rightusesprefix[right + 1]. Writingprefix[right]leaves out the last element. - Arrays start empty, not filled with zeros.
new Array(n + 1)creates empty slots, and adding to one givesNaN. Calling.fill(0), as above, or starting from[0]and pushing both avoid that. - Type annotations don't change the numbers. Types are erased when the code compiles, and
numberis a double. Sums stay exact as long as they remain below 2^53, which is far beyond ordinary inputs. - Updates are costly. If an element changes, every later partial sum changes with it. Partial sums suit arrays that are built once and queried many times.
Key takeaways
- Build
prefixonce inO(n), withprefix[0] = 0andprefix[i + 1] = prefix[i] + nums[i]. - The sum of
nums[left..right]isprefix[right + 1] - prefix[left], inO(1). - Adding 1 per matching element turns the same idea into counting.
- A subarray sum is a difference of two partial sums, which is the key to problems like the maximum sum subarray.