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;
}