計算數組矩形區域中的數值總和

Question

我有很多數值非常大的數組，並將其存儲在row-major 1d array中。

ex: 
    1 2 3 
    4 5 6 

將店int* array = {1,2,3,4,5,6};

什麼，我要做的就是給予row1, row2, column1, column2，然後打印出該地區的總和，它將請求caulate不同區域多次。

什麼，我已經想這是第一次使用嵌套循環遍歷數組和每行的總和存儲在sum_row和每一列的總和存儲在sum_column和存儲元件的整體的總和IM totalSum。

然後totalSum - the row and the columns that surrond it + the elemnts that has been minus twice。

但似乎不夠快，沒有任何的算法，可以做得更快或者一些編碼風格的提示，可以使小的因素？

Thx提前。

Answer 1

在我看來，你已經用另一個迭代代替了一次迭代。問題在於減去「the elemnts that has been minus twice」;除非我弄錯了，否則這需要對這些元素進行迭代求和。

相反，只需遍歷需要求和的矩形區域即可。我懷疑它會變慢。

通過生成相加的左上矩陣矩陣可以獲得更高效的算法。 （請參閱有關summed area table的維基百科文章。）然後，您可以通過查找四個面積總和來計算任意小矩陣總和。