How to find sum of elements from given index interval (i, j) in constant time?

Given an array. How can we find sum of elements in index interval (i, j) in constant time. You ar开发者_StackOverflowe allowed to use extra space.

Example:

A: 3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1

length = 14

int getsum(int* arr, int i, int j, int len);
// suppose int array "arr" is initialized here
int sum = getsum(arr, 2, 5, 14);

sum should be 10 in constant time.

---

If you can spend O(n) time to "prepare" the auxiliary information, based on which you would be able calculate sums in O(1), you could easily do it.

Preparation (O(n)):

aux[0] = 0;
foreach i in (1..LENGTH) {
  aux[i] = aux[i-1] + arr[i];
}

Query (O(1)), arr is numerated from 1 to LENGTH:

sum(i,j) = aux[j] - aux[i-1];

I think it was the intent, because, otherwise, it's impossible: for any length to calculate sum(0,length-1) you should have scanned the whole array; this takes linear time, at least.

---

It cannot be done in constant time unless you store the information.

You would have to do something like specially modify the array to store, for each index, the sum of all values between the start of the array and this index, then using subtraction on the range to get the difference in sums.

However, nothing in your code sample seems to allow this. The array is created by the user (and can change at any time) and you have no control over it.

Any algorithm that needs to scan a group of elements in a sequential unsorted list will be O(n).

---

Previous answers are absolutely fine for the question asked. I am just adding a point, if this question is changed a bit like:

Find the sum of the interval, if the array gets changed dynamically.

If array elements get changed, then we have to recompute whatever sum we have stored in the auxiliary array as mentioned in @Pavel Shved's approach. Recomputing is O(n) operation and hence we need to reduce the complexity down to O(nlogn) by making use of Segment Tree.

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

---

There are three known algorithms for range based queries given [l,r]

1.Segment tree: total query time O(NlogN) 2.Fenwick tree: total query time O(NlogN) 3.Mo's algorithm(square root decomposition)

The first two algorithms can deal with modifications in the list/array given to you. The third algorithm or Mo's algorithm is an offline algorithm means all the queries need to be given to you prior. Modifications in the list/array are not allowed in this algorithm. For implementation, runtime and further reading of this algorithm you can check out this Medium blog. It explains with code. And a very few people actually know about this method.

---

this question will solve O(n^2)time,O(n)space or O(n)time,O(n)space..

Now the best optimal solution in this case (i.e O(n)time,O(n)) suppose a[]={1,3,5,2,6,4,9} is given if we create an array(sum[]) in which we kept the value of sum of 0 index to that particular index.like for array a[],sum array will be sum[]={1,4,9,11,17,21,30};like {1,3+1,3+1+5......} this takes O(n)time and O(n) space.. when we give index then it directly fetch from sum array it means add(i,j)=sum[j]-sum[i-1]; and this takes O(1) times and O(1) spaces... so,this program takes O(n) time and O(N) spaces..

int sum[]=new int[l];

    sum[0]=a[0];
    System.out.print(cumsum[0]+" ");
   for(int i=1;i<l;i++)
   {
       sum[i]=sum[i-1]+a[i];
       System.out.print(sum[i]+" ");
   }  

?* this gives 1,4,9,11,17,21,30 and take O(n)time and O(n) spaces */

sum(i,j)=sum[j]-sum[i-1]/this gives sum of indexes from i to j and take O(1)time and O(1) spaces/

so,this program takes O(n) time and O(N) spaces..emphasized text