c++ - 计算数组矩形区域中的值的总和

Question

我有一个非常大的数组，包含许多值并将其存储在row-major 1d array.

ex:  
   1 2 3  
   4 5 6

将存储在int* array = {1,2,3,4,5,6};

我要做的是给出row1, row2, column1, column2，然后打印出面积的总和，它会要求多次计算不同的面积。

我想到的是首先使用嵌套循环遍历数组并将每一行的总和存储在sum_row其中，并将每一列的总和存储在sum_column其中并存储总元素的总和 im totalSum。

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

但它似乎足够快，是否有任何算法可以做得更快或一些编码风格的提示可以让这个因素变得很小？

提前谢谢。

Answer 1

在我看来，您已经用另一个替换了一个双重迭代。问题在于减去“ the elemnts that has been minus twice”；除非我弄错了，否则这涉及迭代这些元素以对它们求和。

相反，只需遍历需要求和的矩形区域。我怀疑它会更慢。

通过生成求和的左上矩阵的矩阵可以获得更有效的算法。（请参阅关于总面积表的 Wikipedia 文章。）然后，您可以通过查找四个面积总和来计算任何子矩阵总和。