找到矩陣中任意矩形的總和的最快方法

我有一個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

找到矩陣中任意矩形的總和的最快方法

回答

相關問題