Prefix Sum 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.

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:

public static int[] prefixSums(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        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: