The idea
A partial sum, also called a prefix sum, is the sum of the first few elements of an array. If you compute all of them once, you can answer "what is the sum of the elements from index l to index r?" with a single subtraction instead of a loop.
Take nums = [3, 1, 4, 1, 5, 9, 2, 6]. Summing nums[2..5] directly means adding 4 + 1 + 5 + 9 = 19, and for a long range that means touching every element in it. If a lot of such questions are asked about the same array, the repeated work adds up. Partial sums pay a one-time O(n) cost, after which every range sum takes O(1).
Building the prefix array
Create an array prefix with one extra slot, where prefix[i] holds the sum of the first i elements. So prefix[0] is 0 (the sum of nothing), and each next entry adds one more element:
val nums = intArrayOf(3, 1, 4, 1, 5, 9, 2, 6)
val prefix = IntArray(nums.size + 1)
for (i in nums.indices) {
prefix[i + 1] = prefix[i] + nums[i]
}
println(prefix.toList())
[0, 3, 4, 8, 9, 14, 23, 25, 31]
A new IntArray(n) is filled with zeros, so prefix[0] is already 0. The extra leading zero is what makes the range formula work for ranges that start at index 0, with no special case.
Answering a range query
The sum of nums[l..r], both ends included, is prefix[r + 1] - prefix[l]. The first term is the sum of everything up to and including r. Subtracting the sum of everything before l leaves exactly the elements from l to r.
fun rangeSum(l: Int, r: Int): Int = prefix[r + 1] - prefix[l]
println(rangeSum(2, 5)) // 19
println(rangeSum(0, 7)) // 31
println(rangeSum(3, 3)) // 1
These values match direct addition: 4 + 1 + 5 + 9 is 19, the whole array sums to 31, and a single element is itself.
Kotlin tools
The loop above is the version to learn, but the standard library has a shortcut. runningFold keeps a running result and returns every intermediate value, and scan is an alias for it:
println(nums.runningFold(0) { acc, x -> acc + x })
[0, 3, 4, 8, 9, 14, 23, 25, 31]
It returns a List<Int>, not an IntArray, and the starting value 0 gives the same leading zero. runningReduce is the version without a starting value, so its result has no leading zero and is the same length as the input.
Watch the type: Int overflows
An Int is 32 bits and overflow wraps silently. Sums of large values can leave its range even when each element fits:
val big = intArrayOf(2_000_000_000, 2_000_000_000)
var s = 0
for (x in big) s += x
println(s) // -294967296
var t = 0L
for (x in big) t += x
println(t) // 4000000000
When the total might exceed about 2.1 billion, use a LongArray for the prefix sums, and start running totals with 0L. Adding an Int to a Long is allowed and gives a Long.
Where partial sums help
Partial sums turn a repeated inner loop into a subtraction. They are the tool for:
- many range-sum queries on a fixed array;
- checking whether some subarray adds up to a target, by looking for two prefix values that differ by that target;
- comparing the sums of the left and right parts around a position, since the left part is a prefix and the right part is the total minus a prefix.
They do not help when the array keeps changing between queries, because every update would make the stored prefix values stale.
Common mistakes
- Off-by-one in the formula. With the extra leading zero, the sum of
nums[l..r]isprefix[r + 1] - prefix[l]. Writingprefix[r] - prefix[l]leaves outnums[r]. - Making
prefixthe same size asnums. Then there is no slot for the empty prefix and ranges starting at 0 need special handling. - Using
Intfor big sums. The wrapped result looks like a valid number, so no error shows. - Recomputing the prefix inside the query. The point is to build it once.
Key takeaways
- Build
prefixonce inO(n)with one extra leading 0. - Each range sum is
prefix[r + 1] - prefix[l], inO(1). - Choose
Longwhen the sums can pass theIntlimit. - The next lessons use the same idea to count and compare subarrays quickly.