What partial sums are
A partial sum, also called a prefix sum, is the sum of the first few elements of an array. Take nums = {3, 1, 4, 1, 5, 9, 2, 6}. The partial sum after two elements is 3 + 1 = 4, and after five elements it is 3 + 1 + 4 + 1 + 5 = 14.
The technique is to compute all of these once, store them in an array, and then answer any "sum of a stretch of the array" question with one subtraction. Without it, each such question needs a loop over the stretch. With a million queries on a large array, that difference decides whether the program finishes.
Building the prefix array
The usual layout makes the prefix array one element longer than the input. Element prefix[i] holds the sum of the first i elements of nums, so prefix[0] is 0, the sum of nothing.
int[] nums = {3, 1, 4, 1, 5, 9, 2, 6};
long[] prefix = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
Console.WriteLine(string.Join(", ", prefix));
This prints:
0, 3, 4, 8, 9, 14, 23, 25, 31Each entry is the previous one plus the next input element, so building the whole array takes one pass and O(n) time. The extra space is also O(n).
Answering range queries
The sum of nums[left..right], both ends included, is everything up to right minus everything before left:
sum(left, right) = prefix[right + 1] - prefix[left]For the indices 2 to 5, the elements are 4, 1, 5 and 9. The formula gives prefix[6] - prefix[2] = 23 - 4 = 19, and adding the four elements by hand also gives 19. Wrapped in a small class, the idea looks like this:
class RangeSum {
private readonly long[] prefix;
public RangeSum(int[] nums) {
prefix = new long[nums.Length + 1];
for (int i = 0; i < nums.Length; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
// sum of nums[left..right], both ends included
public long Sum(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}
With the array above, Sum(2, 5) returns 19, Sum(0, 7) returns 31 and Sum(3, 3) returns 1. After the O(n) setup, every query costs O(1), no matter how long the stretch is.
Why the extra leading zero
If the prefix array had the same length as the input, a query starting at index 0 would need prefix[left - 1], which is prefix[-1], and C# would throw an IndexOutOfRangeException. The leading zero removes that special case: prefix[0] stands for "the sum before the first element".
C# details that matter
- Overflow is silent. Arithmetic on
intwraps around by default instead of reporting an error. Two values ofint.MaxValueadded in anintvariable give -2, while alongholds the exact total, 4294967294. When the sums could reach a few billion, store the prefix sums in along[], as above. When the data is small, plainintis fine. - Arrays have a fixed length. The size of
prefixis set when it is created, which is why it is allocated withnums.Length + 1. - Elements start at zero. A new
long[]is filled with zeros, soprefix[0]needs no assignment. - Inclusive or exclusive ends. The formula above uses inclusive
leftandright. Many programs use an exclusive end instead, where the sum isprefix[end] - prefix[start]. Pick one convention and stay with it.
Running sums without an array
Sometimes you don't need to keep every prefix, only the current one. A single variable that is updated in a loop is enough:
int[] values = {1, -2, 3};
int run = 0;
foreach (int v in values) {
run += v;
Console.Write(run + " ");
}
This prints:
1 -1 2 That is the partial sum after one, two and three elements, computed in O(1) extra space. Many problems in this chapter work this way: the loop keeps a running sum, and combines it with one or two other values that are also updated as it goes.
Where this chapter goes next
The next lessons use partial sums on problems about subarrays, the continuous stretches of an array. The key fact is the one above: a subarray sum is the difference of two prefix sums. A question like "which subarray has the largest sum?" then becomes "which pair of prefix positions has the largest difference, with the smaller one first?". You can answer it in a single pass by tracking the running prefix sum and the smallest prefix seen so far. The Maximum Sum Subarray lessons build on that idea.
Key takeaways
prefix[i]is the sum of the firstielements, andprefix[0]is 0.- Build it in one pass with
prefix[i + 1] = prefix[i] + nums[i]. - The sum of
nums[left..right]isprefix[right + 1] - prefix[left], in constant time. - Use
longwhen sums may exceed theintrange, becauseintoverflow wraps silently. - When only the latest prefix matters, a single running variable replaces the array.