algorithm - Calculate the sum of elements in a matrix efficiently

Question

In an interview I was asked if I was given an n*m matrix how to calculate the sum of the values in a given sub-matrix (defined by top-left, bottom-right coordinates).

I was told I could pre-process the matrix.

I was told the matrix could be massive and so could the sub-matrix so the algo had to be efficient. I stumbled a bit and wasn't told the best answer.

Anyone have a good answer?

Answer 1

This is what Summed Area Tables are for. http://en.wikipedia.org/wiki/Summed_area_table

Your "preprocessing" step is to build a new matrix of the same size, where each entry is the sum of the sub-matrix to the upper-left of that entry. Any arbitrary sub-matrix sum can be calculated by looking up and mixing only 4 entries in the SAT.

EDIT: Here's an example.

For the initial matrix

0 1 4
2 3 2
1 2 7

The SAT is

0 1 5
2 6 12
3 9 22

The SAT is obtained using S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1),

where S is the SAT matrix and a is the initial matrix .

If you want the sum of the lower-right 2x2 sub-matrix, the answer would be 22 + 0 - 3 - 5 = 14. Which is obviously the same as 3 + 2 + 2 + 7. Regardless of the size of the matrix, the sum of a sub matrix can be found in 4 lookups and 3 arithmetic ops. Building the SAT is O(n), similarly requiring only 4 lookups and 3 math ops per cell.