BS | @bskokdev
Github

# Prefix sum

## Overview

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 `prefix_sum` = `15`.

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.

## Useful formulas

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:

```.css-ce1lkk{background-color:var(--theme-ui-colors-background);border:none;color:var(--theme-ui-colors-text);cursor:pointer;font-size:14px;font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Helvetica Neue",Arial,"Noto Sans",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji";letter-spacing:0.025rem;-webkit-transition:all 0.3s ease-in-out;transition:all 0.3s ease-in-out;position:absolute;right:0;z-index:1;border-radius:0 0 0 0.25rem;padding:0.25rem 0.6rem;}@media screen and (min-width: 640px){.css-ce1lkk{font-size:14px;}}@media screen and (min-width: 768px){.css-ce1lkk{font-size:16px;}}.css-ce1lkk[disabled]{cursor:not-allowed;}.css-ce1lkk:not([disabled]):hover{background-color:var(--theme-ui-colors-primary);color:var(--theme-ui-colors-white);}```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.

#### Sum queries

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 `R` and `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.