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

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.