找到矩阵中任何矩形之和的最快方法

Question

我有amxn矩阵,希望能够计算任意矩形子矩阵的总和.对于给定的矩阵,这将发生几次.我应该使用什么数据结构？

例如,我想在矩阵中找到矩形的总和

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

总和是68.

我要做的是逐行累积它:

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

然后,如果我想找到矩阵的总和,我只需积累 28,32,36,40 = 136.只有四个操作而不是15个.如果我想找到第二和第三行的总和,我只累加15,18,21,24并减去1,2,3,4 = 6 + 8 + 10 + 12 + 15 + 18 + 21 + 24 = 68.但在这种情况下,我可以使用另一个矩阵,按列累积这个矩阵:

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

在这种情况下,我只是总和26和42 = 68.只有2次操作而不是8次.对于更宽的子矩阵,使用第二种方法和矩阵是有效的,对于更高的第一种方法和矩阵.我能以某种方式将这种方法拆分为一个矩阵吗？

所以我只是总结并减去另外两个？

Answer 1

你的方法几乎就在那里.解决方案是使用求和区域表(也称为积分图像):

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

关键的想法是你通过矩阵进行一次遍历并累积,使得"求和面积表中任意点(x,y)的值只是(x,y)左上方和左边所有像素的总和, 包括的.".

然后,您可以使用四次查找以恒定时间计算任何矩形内的总和.