找到矩阵中任意矩形的总和的最快方法

我有一个m×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 = 。但在这种情况下，我可以用另一种基质，积累这一个由列：

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

在这种情况下我刚总结和 = 。只有2个操作而不是8个。对于更宽的子矩阵来说，使用第二种方法和矩阵是有效的，对于更高的第一个。我可以以某种方式拆分合并这种方法到一个矩阵？

所以我只是总结角落，减去另外两个？

来源

2014-02-28 JohnDow

你几乎在那里用你的方法。该解决方案是使用积分图（又名整体形象）：

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

的核心思想是你做一个穿过你的矩阵和积累，使得“在任何一点的值（ x，y）的总和就是（x，y）以上和左边所有像素的和。“。

然后，您可以在四个查找的同一时间内计算任意矩形内的和。

来源

2014-02-28 13:08:09 YXD

如果有* sum * sum查询遍历整个或部分矩阵，这是有利的。 – mvw

在我的情况下，它是显着的大数目和 – JohnDow

是否有快速的Java实现？如果我这样做brute force =>递归 - 它非常缓慢。 – JohnDow

为什么不能用For循环添加它们？

int total = 0; 
for(int i = startRow; i = endRow; i++) 
{ 
    for(int j = startColumn; j = endColumn; j++) 
    { 
     total += array[i][j]; 
    } 
}

你在哪里子阵（ “矩形”）将从STARTROW去endRow（宽度）和STARTCOLUMN到ENDCOLUMN（高度）。

来源

2014-02-28 13:10:28 CoryKramer

如果我想在N = 1000的矩阵NxN中找到100个子矩阵的和呢？ – JohnDow

然后你把上面的代码放到一个名为 SumSubarray（int startRow，int endRow，int startCol，int endCol）的函数中，然后为每个子矩阵调用它，然后添加结果。 – CoryKramer

@JohnDow对于一次计算网络是正确的。如果你想优化多个子数目在你的问题中提到它（我没有看到它） – mvw

找到矩阵中任意矩形的总和的最快方法

回答

相关问题