Close

# Partial sum queries

Given an array of numbers, we need to answer many queries of the form `Sum(A[i]...A[j])`,
For example, let the array be `[15, 6, 1, 12, 7, 4, 10]`
```Sum(A[1:3]) = 15+6+1 = 22 Sum(A[4:6]) = 12+7+4 = 23 ...```
The simplest solution is to iterate through the elements from i to j and return the sum.
However this will be good enough if we have a small number of queries. What if we need to run many queries?
In worst case this is takes O(n2) time.
How can we reduce the time complexity?
If we pre-process the array by calculating the prefix array, we can answer each query in O(1) time.
For the above example calculate the prefix array by using the formula ```Prefix[i] = Prefix[i-1]+A[i] ```
`Prefix = [15, 21, 22, 34, 41, 45, 55]`
Now the partial sums can be calculated as follows
```Sum(A[i:j]) = Prefix[j] - Prefix[i-1] if i > 1 = Prefix[j] if i=1 ```
Here is the Java function which implements the above
```long partialSum(int []prefixArr, int start, int end) { long sum = arr[end]; if( start > 0) sum -= arr[start-1]; return sum; }```