Quick Links

*Written By :* **Shivani Tiwari**

Range Sum is a popular problem in competitive programming and technical interviews. Range Sum problem asks sum of the elements in a range in a given array. Naïve approach requires O(N*Q) time which can be improved to be O(N+Q) using Prefix Sum approach. N is the size of the array and Q is the number of queries.

Prefix Sum technique is used to *give range sum in an array in O(1) for each query with a one time pre-processing.*

*Let’s* *see* *an* *example* *for* *this* *with* *a* *basic* *statement*.

*Suppose you are given with an array of N integers (both negative and positive) and Q queries. Each query is of the form of two integers L and R where you have to find the sum of all the integers between L and R (inclusive).** Constraints : *(N <= 10^5) , (1 <= L, R <= 10^5) and (Q <= 10^5)

**N=7, Q=3**

*Example*:**arr[]={4,5,-7,11,13,15,1}**

*Given Array :***arr–>**

Sum of arr[0] to arr[4] is : 4+5+(-7)+11+13 = 26

Sum of arr[1] to arr[7] is : 5+(-7)+11= 9

Sum of arr[3] to arr[6] is : (-7)+11+13+15+1= 33

*Naive Approach*

For each query, let’s take a variable *sum_range = 0 *and run a loop from L to R index and *store the sum* in sum_range. We can do this for each query.

We will end up traversing the entire array length and there are Q such queries. So the ** time complexity **would be

**Therefore, this approach is inefficient.**

*O(N*Q)*.*Prefix Sum Approach*

### Pre-processing

Before answering any query, let’s calculate the cumulative sum of the array and store it in the array (let’s say ** prefix_array**). The code for creating a prefix array would look like this :

```
prefix_array[1] = a[1]
{
for(i = 2; i <= n; ++i) {
prefix_array[i] = prefix_array[i-1] + a[i];
}
}
```

**prefix_array–>**

After creating this prefix array, each query of range (L, R) can be answered in O(1) by using

sum of arr[L] to arr[R] = *prefix_array[R] – prefix_array[L-1]*

Now the above queries can be answered in O(1) time as follows:

Sum of arr[1] to arr[5] = prefix_array[5] – prefix_array[0]

Sum of arr[2] to arr[4] = prefix_array[4] – prefix_array[1]

Sum of arr[3] to arr[7] = prefix_array[7] – prefix_array[2]

**Key Idea :** *First take the cumulative sum from 0 to R and excluded the sum from 0 to L-1 from it, so the remaining sum is the sum from L to R.*

**Time complexity is O(N+Q).**