arrays - 在大矩阵中查找许多子矩阵的总和？

Question

对于二维矩阵 A，我们想要求出从 (x1,y1) 到 (x2, y2) 坐标的子矩阵之和。

我遇到了这个explanation找到子矩阵和，我可以遵循解决方案的逻辑，直到他们执行以下计算的最后一部分:

sum[x2][y2] + sum[x1][y1] - sum[x1][y2] - sum[x2][y1]

他们的想法是计算一个矩阵，其中每个点代表矩阵的总和，所有这些都引用原始 x1,y1 为 (0,0)。然后使用一些几何方法，他们得到某个子数组的总和。我没有得到的是几何部分。它是如何发挥作用的？为了完整起见，我将绘制数组。

假设我们有这样的 A:

1  2  3


4  5  6


7  8  9

例如，假设在找到矩阵和后我们有以下内容:

1  3  6


5  12  21


12  27  45

假设我要求从(1,1)到(2,2)的子数组的和，其中(0,0)是和10处的原点。那么根据公式，我们有总和

A[2][2] + A[1][1] - A[1][2] - A[2][1]

得出 12 + 45 - 27 - 21 = 9。

哪个不是正确答案，28？

这个答案有问题吗？

Answer 1

计算完您提到的总和后，sum[x][y] 将表示从 (0,0) 到 (x,y) 的矩形的总和.

现在我们要计算从(x1,y1) 到(x2,y2) 的子数组的和。我们从 sum[x2][y2] 开始。我们需要减去 sum[x1-1][y2] 和 sum[x2][y1-1] 因为它们不属于所需的矩形。但是，请注意红色矩形被减去两次，因此我们添加 sum[x1-1][y1-1]