In this post, we will look at prefix sums and how they can be used to solve a common coding problem, that is, calculating the sum of an array (segment). This article will use Java for the code samples but the concept should apply to most programming languages.
Before looking into prefix sums, let’s look at the function below that calculates the sum of an array using a standard for loop. The function iterates the array and adds each value to a variable to get the sum:
Array Segments
Now for array segments, array segments can also be referred to as a slice of an array. Specifically a continuous slice of an array. With some modifications, the previous function can be used to also calculate the array segment sum by adding starting and ending array indexes:
Let’s say we have an array with values [ 10, 7, 22, 2, 13, 15, 6 ] and we want to get the sum of a segment starting from values 7 to 13. The sum should be 44 (7 + 22 + 2 + 13).
Now, let’s use our modified function to calculate the sum of array segment providing the starting index for 7(index=1) and ending index for 13(index=4):
Prefix sums
Now for prefix sums, we can use prefix sums as an alternative approach to the same problem. Prefix sums is a simple yet powerful technique that we can use to easily calculate the sum of a segment or an array. It allows us to lookup the sum of an array segment or for the whole array in constant time, by introducing a reusable lookup array. Given the same array from above, its prefix sum should be like:
Now that we know what prefix sums look like, let’s use it to calculate the sum of an array segment of the original array. Using the same example array segment as earlier, the segment that starts from index 1 and ends in index 4 that have the sum of 44.
When using prefix sums, iterating each array value won’t be needed anymore, we only need two elements for the calculation and we can get those in constant time. We can get the two values using elements from prefix sums array in certain indexes.
The first element is at the index of starting index of the array segment, in this case, it’s index 1, which has the value of 10. The second element is at the index +1 of the ending index of the array segment, in this case, it’s index 4 + 1, so the final index is 5, which has the value of 54. Now that we have our two elements, we can subtract the first element to the second element to get the array segment sum which is 44 (54 - 10).
That is prefix sums, in theory, now let’s write some Java code to create a prefix sum of an array. The input would be the original array and the output would be an array containing values similar to the example above.
There are slight variations on how one should build a prefix sum. In our example, we’re going with initializing it with an array size +1 based from the original array size (n+1). Then each prefix sum value of prefixSum[i] will have a value of prefixSum[i - 1] + originalNums[i - 1] in order for us to have a running sum for the original array:
After creating our prefix sum, we can use it to look up the sum of an array segment(or whole) in constant O(1) time. Let’s build a helper function for that lookup to make our lives easier:
Putting it all together, let’s use prefix sums to calculate the array segment sum for the same sample array above:
In instances where different array segment sums are needed for the same array, prefix sums are most useful. The first approach would have been O(n * m), where m is how many times we need to recalculate different array segments. With prefix sums, our time complexity is reduced to O(n + m).
End
In this post, we learned what are prefix sums, how to implement them, and how they can be applied and used to calculate the sum of an array segment.
Also published at: https://micogongob.com/array-segment-sum-using-prefix-sums