Fastest way to find sum of any rectangle in matrix

Question

I have a m x n matrix and want to be able to calculate sums of arbitrary rectangular submatrices. This will happen several times for the given matrix. What data structure should I use?

For example I want to find sum of rectangle in matrix

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

Sum is 68.

What I'll do is accumulating it row by row:

1   2   3   4
6   8   10  12
15  18  21  24
28  32  36  40

And then, if I want to find sum of the matrix I just accumulate 28,32,36,40 = 136. Only four operation instead of 15. If I want to find sum of second and third row, I just accumulate 15,18,21,24 and subtract 1, 2, 3, 4. = 6+8+10+12+15+18+21+24 = 68. But in this case I can use another matrix, accumulating this one by columns:

1   3   6   10
5   11  18  26
9   19  30  42
13  27  42  58

and in this case I just sum 26 and 42 = 68. Only 2 operation instead of 8. For wider sub-matrix is is efficient to use second method and matrix, for higher - first one. Can I somehow split merge this to methods to one matrix?

So I just sum to corner and subtract another two?

Answer 1

You're nearly there with your method. The solution is to use a summed area table (aka Integral Image):

• http://en.wikipedia.org/wiki/Summed_area_table

The key idea is you do one pass through your matrix and accumulate such that "the value at any point (x, y) in the summed area table is just the sum of all the pixels above and to the left of (x, y), inclusive.".

Then you can compute the sum inside any rectangle in constant time with four lookups.