Introduction to Prefix Sums

Intuition

Imagine keeping track of how much money you spend on takeout meals each day over a period of days.

Let’s say you want to know the total spent on takeout food up until a particular day. For example, you might like to know that the total you’ve spent up until Wednesday is $45 ($10 + $15 + $20). This is information which a prefix sum array can store. For an array of integers, a prefix sum array maintains the running sum of values up to each index in the array.

To obtain the prefix sum at each index, we just add the current number from the input array to the prefix sum from the previous index.

![Image represents a step-by-step calculation of prefix sums for an array. The top row shows the input array [10, 15, 20, 10, 5]. Each element in this array is represented by a vertical orange line pointing downwards. The label ‘prefix_sums = 10’ indicates the initialization of a new array to store the prefix sums. Subsequent rows show the iterative calculation. Each orange line represents the addition of the current element to the running sum. Curved peach arrows indicate the addition operation (+), connecting the previous prefix sum to the current element. The resulting prefix sums are shown in each row within square brackets: [10], [10, 25], [10, 25, 45], [10, 25, 45, 55], and finally [10, 25, 45, 55, 60]. The process demonstrates how each element in the prefix sums array is the cumulative sum of all preceding elements in the input array.

In code, the above process looks like this:

Python

JavaScript

Java

def compute_prefix_sums(nums):
    # Start by adding the first number to the prefix sums array.
    prefix_sum = [nums[0]]
    # For all remaining indexes, add 'nums[i]' to the cumulative sum from the previous
    # index.
    for i in range(1, len(nums)):
        prefix_sum.append(prefix_sum[-1] + nums[i])

As you can see, building a prefix sum array takes O(n)O(n)O(n) time and O(n)O(n)O(n) space, where nnn denotes the length of the array.

Applications of prefix sums
Aside from allowing us to have constant-time access to running sums at any index within an array, prefix sums are commonly used to efficiently determine the sum of subarrays. This application is examined in depth in the problems in this chapter.

Another interesting variant of prefix sums is prefix products, which populates an array with a running product instead of a running sum. Similar to prefix sums, prefix products provide an efficient way to determine the product of subarrays.

Real-world Example

Financial analysis: As hinted at earlier, a real-world use of prefix sums is for financial analysis, particularly in calculating cumulative earnings or expenses over time.

For instance, consider a company’s daily revenue over a month. A prefix sum array can be used to quickly calculate the total revenue for any given period within that month. By precomputing the prefix sums, the company can instantly determine the revenue from day 5 to day 20 without having to sum each day’s revenue individually. This is especially useful for generating financial reports, where quick calculations over various periods are necessary to analyze trends.

Chapter Outline