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

algorithm, arrays

Solution

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.

Problem

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.

Original source