What partial sums are
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, then 3 + 1 = 4, then 3 + 1 + 4 = 8, and so on. Computed once for the whole array and stored, they let you answer "what is the sum of the elements between positions left and right?" in constant time, however long the range is.
The problem they solve is repeated work. Suppose you must answer many such questions about the same array. Adding up the range with a loop costs time proportional to the range length each time. With q queries on an array of n elements that is up to O(n * q). Spending O(n) once on partial sums brings each query down to O(1).
Building the array
The version that makes queries easy has one extra element in front. Let prefix[0] be 0, the sum of no elements, and let prefix[k] be the sum of the first k elements of nums. The array is one longer than nums.
let nums = [3, 1, 4, 1, 5, 9, 2, 6]
var prefix = [0]
for x in nums {
prefix.append(prefix.last! + x)
}
print(prefix) // [0, 3, 4, 8, 9, 14, 23, 25, 31]
Each new entry is the previous entry plus the next element. prefix.last is an optional, because an empty array has no last element, and the ! unwraps it. That is safe here because the array starts as [0] and is never empty.
The same thing can be written with an index:
var sums = [0]
for i in 0..<nums.count {
sums.append(sums[i] + nums[i])
}
print(sums == prefix) // true
A running total without the leading zero is also common. Then prefix2[k] is the sum of the elements from index 0 through k. It has the same length as nums, but a query that starts at index 0 needs a special case.
Answering range queries
The sum of nums[left...right], both ends included, is the sum of the first right + 1 elements minus the sum of the first left elements. Everything before left cancels:
func rangeSum(_ prefix: [Int], _ left: Int, _ right: Int) -> Int {
return prefix[right + 1] - prefix[left]
}
print(rangeSum(prefix, 2, 5)) // 19, which is 4 + 1 + 5 + 9
print(rangeSum(prefix, 0, 7)) // 31, the whole array
print(rangeSum(prefix, 3, 3)) // 1, a single element
The leading 0 is what makes this formula work for every range, including one that starts at index 0, with no special case. The cost of a query is two array reads and one subtraction.
Swift details
- Overflow traps.
Intis 64 bits in Swift. If a total ever goes beyond that, the program crashes instead of wrapping. For ordinary data, such as sums of values up to a few million, there's plenty of room. - Bounds are checked. Reading
prefix[right + 1]whenrightis the last index ofnumsis fine, becauseprefixhasnums.count + 1elements. Reading past it crashes. - Closed and half-open ranges. This lesson's range sums use inclusive bounds, like Swift's
.... For a half-open pairleft..<right, the same idea givesprefix[right] - prefix[left]. - Checking your work.
nums[2...5].reduce(0, +)adds up the same range directly and also gives 19. It is a handy way to test a prefix-sum function on small inputs. - The array is a snapshot. If
numschanges after you buildprefix, the prefix array no longer matches and must be rebuilt.
Where it leads in this chapter
Partial sums are the first tool of this chapter, and many later problems reduce to them. A few typical shapes:
- sum of a range, many times, on a fixed array;
- how many ranges add up to a target, by looking for earlier prefix values that differ from the current one by the target;
- finding a position where the sum on the left equals the sum on the right, by comparing a prefix value with the total minus it.
In each case the step is the same: build the prefix array in one pass, then express the question as a difference of two prefix values.
Key takeaways
- A prefix sum array stores the total of the first
kelements for everyk, built in oneO(n)pass. - With a leading 0, the sum of
nums[left...right]isprefix[right + 1] - prefix[left]. - Each query then costs
O(1)instead ofO(range length). - The prefix array has
nums.count + 1elements, so watch the indices.
