## Prefix Sum

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 - 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:

Question | Difficulty |
---|---|

Count Vowels in Substrings | Medium |

Subarray Sum Equals K | Medium |

Loading comments...