What a partial sum is
A partial sum, also called a prefix sum, is the total of the first few elements of an array. For nums = [3, -1, 4, 1, 5, 9, -2, 6], the partial sums are 3, 2, 6, 7, 12, 21, 19 and 25: each one is the previous partial sum plus the next element.
The idea pays off whenever a problem asks for the sum of a contiguous stretch of elements, a subarray, and asks for it many times. Adding up a stretch element by element costs time proportional to its length. With partial sums computed once, any stretch costs a single subtraction.
Building the prefix array
The standard form uses an array one element longer than the input. Entry prefix[i] holds the sum of the first i elements, so prefix[0] is 0, the sum of nothing. The extra leading zero removes a special case for subarrays that start at index 0.
fn main() {
let nums = vec![3, -1, 4, 1, 5, 9, -2, 6];
let mut prefix = vec![0i64; nums.len() + 1];
for i in 0..nums.len() {
prefix[i + 1] = prefix[i] + nums[i] as i64;
}
println!("{:?}", prefix);
}
[0, 3, 2, 6, 7, 12, 21, 19, 25]
Three Rust details appear here. vec![0i64; n + 1] creates a vector of n + 1 zeros, and the i64 suffix fixes their type. nums.len() is a usize, the type Rust uses for indexes and lengths, and nums[i] as i64 widens each element so it can be added to the running total. The loop writes to prefix[i + 1] and reads prefix[i], which is already filled in.
Answering a range query
The sum of nums[l..=r], from index l to index r inclusive, is the sum of the first r + 1 elements minus the sum of the first l elements:
let (l, r) = (2usize, 5usize);
println!("{}", prefix[r + 1] - prefix[l]);
19
Elements 2 to 5 are 4, 1, 5 and 9, which add up to 19, the same as prefix[6] - prefix[2], that is 21 - 2. The shift by one is the part to get right: the end index is r + 1 because prefix[i] counts i elements, and the start index is l itself.
Building the array costs O(n) time and O(n) space. After that each query is O(1). With q queries the total is O(n + q), instead of O(n * q) for adding the elements each time.
Building it with an iterator
Rust's iterators can build the same array. scan carries a running total through the elements and yields the new total each time:
let p2: Vec<i32> = std::iter::once(0)
.chain(nums.iter().scan(0, |s, &x| {
*s += x;
Some(*s)
}))
.collect();
println!("{:?}", p2);
[0, 3, 2, 6, 7, 12, 21, 19, 25]
std::iter::once(0) supplies the leading zero, chain appends the running totals, and collect gathers the result into the annotated Vec<i32>. The explicit loop is just as good, and often easier to read.
Where it is used
The same subtraction shows up in several problems in this chapter:
- Fixed-length windows. The sum of every window of length
kisprefix[i + k] - prefix[i]. Fork = 3on the array above, the best window is 1, 5, 9 with sum 15. - Best subarray ending here. A subarray ending at position
jhas sumprefix[j + 1] - prefix[i]for some starti. To make it as large as possible, subtract the smallest earlier prefix value. Tracking that minimum as you go gives the maximum subarray sum in one pass. - Taking elements from both ends. A prefix sum covers the front of an array, and the same idea applied to the reversed array covers the back.
- Zero-sum subarrays. Two equal prefix values mean the elements between them add up to zero. Counting repeated prefix values in a
HashMapcounts such subarrays. For[1, -1, 2, -2, 3]there are three.
Rust gotchas
- Overflow. Prefix sums grow with every element, so they overflow sooner than single values do. With
i32elements 2,000,000,000 and 2,000,000,000, ani32total wraps around in an optimized build and gives -294967296, while ani64total gives 4000000000. A debug build panics instead. Use a wider type when the sums can get large. - Off-by-one at the end. The prefix vector has
n + 1entries, so the last valid index isn. Readingprefix[n + 1]panics. usizenever goes negative. Expressions such asr - lori - 1panic in a debug build, or wrap in an optimized one, when the right side is bigger. Check the order of the indexes before subtracting.- Mixed types. Rust won't add an
i32to ani64. Convert withasori64::from(x).
Key takeaways
- A prefix array of length
n + 1with a leading 0 turns any range sum intoprefix[r + 1] - prefix[l]. - Build it once in
O(n), then answer each query inO(1). - Many window and subarray problems reduce to a difference of two prefix values.
- Choose a number type wide enough for the totals, and watch the
usizesubtraction rules.
