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(n^{2}) 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;

}