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.

Answer 2

You can do it by Dynamic programming. Create matrix dp with size n*m. And for each i, j where

1 <= i <= n , 1 <= j <= m  dp[i][j] will be :   dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + values[i][j] 

And for each query we have lx, rx, ly, ry where lx and rx are top-left coordinates, ly and ry bottom-right coordinates of sub-matrix.

1 ≤ lxi ≤ rx ≤ n, 1 ≤ ly ≤ ry ≤ m  sum = dp[rx][ry]  - dp[lx - 1][ry] - dp[rx][ly - 1] + dp[lx-1][ly - 1] 

Look at picture to understand how algorithm works.

OD = dp[rx][ry], OB = dp[lx - 1][ry], OC = dp[rx][ly - 1], OA = dp[lx - 1][ly - 1]