Prefix Sum
Prefix Sum Overview
Count: 10
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:
Solution
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:
Solution
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:
| Done | Question | Difficulty |
|---|---|---|
Medium | ||
Medium |
Mark as read
Your account is free and you can post anonymously if you choose.