算法技巧之计算二维数组区域和

在做算法题目的过程中，经常会遇到二维数组的题目，并且要以二维数组的任意矩形区域的和作为先验知识来进行之后的推算。

例如：已知大小M*N的矩阵A，求矩阵内任意矩形区域的和。

如果采用暴力搜索的方式，则需要O(M^2N^2)的时间复杂度，即需要枚举矩形的左上坐标和右下坐标。采用前缀数组的方式则可以在O(MN)的时间复杂度下得到结果。

前缀数组P：大小为M*N，P[i][j]表示为以(0,0)为左上角，(i,j)为右下角区域的矩形和。

通过前缀数组P，即可以计算原矩阵A内任意矩形区域的和。如计算(x1,y1)到(x2,y2)区域内的和，公式如下：

area = P[x2][y2] - P[x2][y1-1] - P[x1-1][y2] + P[x1-1][y1-1]

当i或j<0时，P[i][j] = 0。图解如下：

可以看到当得到前缀数组后，我们就可以在O(1)的时间内得到任意矩阵区域的数字和。

接下来就是如何得到前缀数组。我们假设前缀数组是按照行优先计算得到的。当计算P[i][j]的时候，前i-1行以及第i行的前j-1个以及得到了。对于A[i][j]这样一个1*1的区域而言，可以用上述公式计算得到：

A[i][j] = P[i][j] - P[i-1][j] - P[i][j-1] + P[i-1][j-1]

因为A[i][j]，P[i-1][j]，P[i][j-1]，P[i-1][j-1]都已知，所以可以计算得到P[i][j]

P[i][j] = A[i][j] + P[i-1][j] +P[i][j-1] - P[i-1][j-1]

因此我们就可以在O(MN)的时间复杂度里得到前缀数组P，整个算法的时间复杂度为O(1)。

前缀数组python代码实现如下(为了避免判断，坐标从(1,1)开始)：

P = [[0 for _ in range(len(A[0])+1)] for _ in range(len(A)+1)]
for i in range(1, len(A)+1):
    for j in range(1, len(A[0])+1):
        P[i][j] = A[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]