— Algorithms — 2 min read
Very useful for calculating sum ranges in an array. We can access the sum up to K elements by looking up the prefix sum of the Kth number.
For example, suppose this int array:
nums = [1,2,3,4,5]
Prefix sum allows us to calculate the sum up to the last element by calling
The prefix sum of the example int array would look like this:
p_sum = [0,1,3,6,10,15].
Note: We use 1-indexed version of the prefix sum array, therefore it stores
n+1 elements where
n is the size of the initial array -
[1,2,3,4,5] is our case.
Since we use 1-indexed version of the prefix sum, we need to calculate with some index offset.
Build a 1-indexed prefix sum
To build the prefix sum array, we would then use this formula on each iteration of i:
nums = [1,2,3,4,5]n = len(nums)prefix_sum =  * (n+1)for i in range(1, n+1):prefix_sum[i] = nums[i-1] + prefix_sum[i-1]
Note: Iteration starts at index 1, so we are within the bounds and goes all the way to the
n+1 since we are in the 1-indexed array. This takes O(n) time to build.
Probably the most common usage of the prefix sum is for answering sum queries on a given range. Suppose again we have an int array
nums = [1,2,3,4,5] (0 indexed) and we want to calculate the sum of numbers at indexes 2-4 - let's call them
L pointers, where
R = 2 and
L = 4.
We can just simply build the prefix sum using the previous formula and then subtract
R+1 from the
L pointer values. We use
R+1 because remember, we use 1-indexed prefix sum, therefore, the offset is necessary.
Therefore, the formula for answering the queries on a given range is this:
range_sum = prefix_sum[R+1] - prefix_sum[L]
Note: You can certainly use 0-indexed prefix sum, however, you need to be careful with the indexes. I find using the 1-indexed prefix sum a bit more intuitive though as we can just say to get the prefix sum of first K elements.
Don't forget sums are not the only use case - products, frequency counts can also be solved by using the prefix sum.