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

Question

我有一个 m x n 矩阵，希望能够计算任意矩形子矩阵的总和。对于给定的矩阵，这将发生多次。我应该使用什么数据结构？

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

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), 包括在内。”.

然后您可以通过四次查找在常数时间内计算任何矩形内的总和。