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

Question

Given an array. How can we find sum of elements in index interval (i, j) in constant time. You are 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.

Answer 1

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).

Answer 2

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.