How to pre-process an integer array to find an average of any subarray in O(1)?

Question

This problem rephrases an interview question. Since this original problem seems too hard to me I am trying to solve a simpler one: how to process an integer array to find an average of any sub-array in constant time. Obviously, we can process all sub-arrays in O(n^2). Are there better solutions?

Answer 1

For the 1d case: compute the cumulative sums of the array, i. e. given array a, define b by

b[0] = a[0];
for (int i = 1; i < n; ++i)
    b[i] = b[i - 1] + a[i];

To compute any average of a subarray, compute the difference of the cumultaive sum corrseponding to the end index and the one corresponding to the start index, and divide by the number of entries in the subarray. For example for the range from i+1 to j, do

average = (b[j] - b[i]) / (double)(j - i);

The same thing works in two dimensions by computing cumulative sums along the two axes.

Answer 2

I would use index zero of each subarray (or a new single-dimension array of the length of the first dimension of the jagged array) to store the average, and compute that average while elements are added to the array. You can compute an average of N+1 items, given an average of N items and the +1 item, in constant time by weighting the existing average by the N items composing it. That means populating the array is still linear, and once populated you have the average in indexed memory (effectively constant-time retrieval).

EDIT: The constant-time average method isn't just "pretty close"; it can be mathematically proven that the average of N items multiplied by N, plus another item, divided by N+1, is exactly equal to the average of N+1 items in the general case. The average of a set S, multiplied by its cardinality N, equals the sum of the set S, so for any nonempty set S of cardinality N:

avg(S) = sum(S) / count(S)
S' = S + {X}
avg(S') = sum(S') / count(S')
        = (sum(S) + X) / count(S')
        = ((avg(S) * N) + X) / count(S') //QED

EDIT AGAIN: Oops: my solution is for a multi-dimensional jagged array. OK, no biggie. In this case, I would create an array containing the cumulative sum for each element of all elements from the first to the current. Then, to calculate the average of any contiguous sub-array, subtract the cumulative sum of the element before the beginning index (or zero if beginning from the first index) from the cumulative sum of the ending index, and divide by the difference between the beginning and ending indexes plus 1.

... which is Sven's answer.