Start learning free

SCALA · PARTIAL SUMS #1

Partial Sums Theory in Scala, explained

What partial sums are

Suppose you have an array of numbers and you need the sum of many different slices of it. Adding the elements of a slice from scratch each time costs time proportional to the slice length. If there are q queries over an array of n numbers, that is up to O(n * q) work.

Partial sums, also called prefix sums, remove the repeated work. You make one pass over the array and store, for each position, the sum of everything before it. After that, any slice sum is a single subtraction.

Building the prefix array

Let nums have n elements. Make an array prefix with n + 1 elements, where prefix(k) is the sum of the first k elements. So prefix(0) is 0, the sum of nothing, and prefix(n) is the sum of the whole array:

val nums = Array(3, 1, 4, 1, 5, 9, 2, 6)
val prefix = new Array[Int](nums.length + 1)
for (i <- nums.indices) {
  prefix(i + 1) = prefix(i) + nums(i)
}
println(prefix.mkString(", "))

0, 3, 4, 8, 9, 14, 23, 25, 31

Several Scala details are at work here:

  • new Array[Int](n) creates an array of n integers, all starting at 0. That is why prefix(0) is already correct.
  • Elements are read and written with parentheses: prefix(i + 1) = ....
  • nums.indices is the range 0 until nums.length.
  • Printing an array with println shows an object reference, so mkString turns it into readable text.

The standard library can build the same array in one call. nums.scanLeft(0)(_ + _) starts from 0 and adds each element to the running total, producing all the partial sums, and it gives the same nine values as the loop above. The loop is the version to practise, because it shows the recurrence: each entry is the previous entry plus one element.

Answering a range query

To get the sum of nums(l) through nums(r), both included, subtract two prefix values:

def rangeSum(l: Int, r: Int): Int = prefix(r + 1) - prefix(l)

println(rangeSum(2, 5))  // 4 + 1 + 5 + 9
println(rangeSum(0, 7))  // the whole array
println(rangeSum(3, 3))  // a single element

19
31
1

The reasoning: prefix(r + 1) is the sum of everything up to and including index r, and prefix(l) is the sum of everything before index l. Subtracting leaves exactly the elements from l to r. The extra leading zero in the array means the case l = 0 needs no special handling, because prefix(0) is 0.

Building the array costs O(n) time and O(n) space. Every query afterwards costs O(1), so q queries cost O(n + q) altogether.

Common mistakes

  • Off-by-one in the formula. With the leading zero, the range l..r is prefix(r + 1) - prefix(l). Using prefix(r) - prefix(l) leaves out nums(r).
  • Overflow. An Int holds about 2.1 billion at most, and an overflow wraps silently. Array(2000000000, 2000000000).sum gives -294967296. When sums can grow large, store the prefix array as Long: new Array[Long](n + 1). Adding an Int to a Long widens the result automatically, so p(i + 1) = p(i) + nums(i) compiles and gives 4000000000 for that input.
  • Recomputing the sum for each query. A loop with slice(l, r + 1).sum returns the same answers but costs O(r - l) per query.
  • Confusing exclusive and inclusive ends. Scala's slice(from, until) excludes its end, while the formula above takes an inclusive end r. Decide which convention you use and keep it.

Key takeaways

  • A prefix array of size n + 1 stores the sum of the first k elements at index k, with prefix(0) = 0.
  • Build it once in O(n); then each range sum is prefix(r + 1) - prefix(l) in O(1).
  • In Scala, use new Array[Int](n + 1) or scanLeft, index with parentheses and switch to Long when sums can pass about two billion.
  • The technique fits any task that asks many times for the total of a slice of a fixed array.
Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free