Prefix Sums - Pattern Overview

A prefix-sum is a technique for efficiently calculating the sum of subarrays in an integer array.

Let’s say we have the following array:

And we want to find the sum of this subarray between index 3 and 5 (inclusive):

We can note that the sum of that subarray (13) is the difference between the sum of two other subarrays (21 - 8 = 13):

The values 8 and 21 are examples of prefix-sums, as they represent the sum of all the elements starting from the first element up to a certain index in the array.

8 = arr[0] + arr[1] + arr[2] 21 = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] + arr[5]

This is the intuition behind the prefix-sum technique. If we have each prefix-sum of an array, we can use them to calculate the sum of any subarray in O(1) time.

Calculating Prefix Sums

We can calculate the prefix-sums of an array in O(n) with the following algorithm:

def prefix_sums(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]
    return prefix

Once we have those prefix sums, to calculate the sum of a subarray between indexes i and j, we use the following formula:

prefix[j + 1] - prefix[i]

Here’s a visual to help you remember and understand the formula:

Time Complexity

Time Complexity: O(n) to calculate the prefix-sums as we have to iterate through the array once. After that, calculating the sum of any subarray takes O(1) time.

Space Complexity: O(n) to store the prefix-sums.

Practice Problems

Work through these practice problems to get more familiar with the prefix sum: