矩阵区域和是一道经典的二维前缀和求解问题给定一个m*n的矩阵mat和一个整数k对于矩阵中的每个位置(i,j)需要计算以该位置为中心、边长为2k1的正方形区域内所有元素的和当边界超出矩阵时会被截断。简单来说就是给矩阵的每个位置画一个框框的大小由k决定然后把框里的所有数字加起来。以示例1的中心位置(1,1)为例k1覆盖了周围3*3的所有元素和为12345678945。求任意一个子矩阵的和可以通过二维前缀和来进行求解构建一个前缀和矩阵dp其中dp[i][j]表示原矩阵从(0,0)到(i-1,j-1)这个子矩阵的所有元素之和。int mmat.size(),nmat[0].size(); vectorvectorint dp(m1,vectorint(n1,0));vectorvectorint dp(m1vectorint(n1,0))构建二维前缀和数组dp多开一行一列方便处理边界问题可通过容斥原理推出dp[i][j]的递推表达式。dp[i][j]表示从原矩阵左上角(0,0)到(i-1,j-1)这个矩形内所有数的和可以把dp[i][j]看成这三部分组成dp[i-1][j]、dp[i][j-1]、mat[i-1][j-1]如下图所示1、上面区域dp[i-1][j]即前i-1列前j列。2、左边区域dp[i][j-1]即前i行前j-1列。右下角单独格子mat[i-1][j-1]如果直接将这三部分加起来会发现左上角区域即dp[i-1][j-1]被多加了一次需要将其减掉故最终dp[i][j]的递推表达式为dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1]。因此二维dp需多开一行一列这样在计算第一行和第一列时能安全地用到dp[0][j]或dp[i][0]这些为0的空区域。class Solution { public: vectorvectorint matrixBlockSum(vectorvectorint mat, int k) { int mmat.size(),nmat[0].size(); vectorvectorint dp(m1,vectorint(n1)); for(int i1;im;i) { for(int j1;jn;j) { dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1]; } } } };有了递推公式dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1]通过两层for循环就可以对dp数组进行填充使得dp[i][j]表示原矩阵从左上角到第i-1行第j-1列的所有元素之和。有了前缀和数组dp之后就可以通过dp来快速推出某个位置(i,j)的区域和如下图所示首先分别确定以(i,j)为中心半径为k的矩阵区域左上角、右下角的坐标需要注意坐标是否越界即左上角坐标为(max(i-k,0),max(j-k,0))右下角坐标为(min(ik,m-1),min(jk,n-1))。映射到dp由于dp多增了一行一列故左上角坐标(x1,y1)、右下角坐标(x2,y2)需相应1。问题就转化为已知一个子矩阵上边界为x1-1下边界为x2-1左边界为y1-1右边界为y2-1求这个子矩阵内所有数的和。映射到dp坐标相应加1如下图所示要计算(x1,y1)到(x2,y2)的区域和可以转化为先求(0,0)到(x2,y2)这块大矩形的区域和该区域包含了四部分如下图所示该区域包含了目标区域但多了几块多余的部分1、上半部分dp[x1-1][y2]2、左半部分dp[x2][y1-1]根据容斥原理用大矩形dp[x2][y2]减掉上半部分dp[x1-1][y2]、左半部分dp[x2][y1-1]此时二者重叠部分dp[x1-1][y1-1]被多减了一次要加回来就求出了目标区域的和即retdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]。代码实现class Solution { public: vectorvectorint matrixBlockSum(vectorvectorint mat, int k) { int mmat.size(),nmat[0].size(); vectorvectorint dp(m1,vectorint(n1)); for(int i1;im;i) { for(int j1;jn;j) { dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1]; } } vectorvectorint res(m,vectorint(n)); for(int i0;im;i) { for(int j0;jn;j) { int x1max(0,i-k)1,x2min(m-1,ik)1; int y1max(0,j-k)1,y2min(n-1,jk)1; res[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]; } } return res; } };在原来代码的基础上vectorvectorint res(m,vectorint(n))创建一个与原矩阵相同大小的矩阵res通过for循环再次遍历原矩阵的每个位置(i,j)int x1max(0,i-k)1,x2min(m-1,ik)1;int y1max(0,j-k)1,y2min(n-1,jk)1;根据参数k计算出以该位置(i,j)为中心的矩阵边界1转化为在dp数组中的索引ret[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]最后通过容斥原理利用四个前缀和O(1)求得该区域的和并存入res[i][j]中return res即可。整个算法的时间复杂度为O(m*n)空间复杂度也为O(m*n)。矩阵区域和的本质是通过二维前缀和来求解而二维前缀和的核心就是容斥原理分为两步构建前缀和数组dp时dp[i][j]表示从原矩阵左上角(0,0)到(i-1,j-1)的矩形和要得到dp[i][j]可以通过容斥原理把上方区域dp[i-1][j]、左方区域dp[i][j-1]和当前格mat[i-1][j-1]加起来但此时左上角dp[i-1][j-1]被重复加了一次因此要减掉即dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1]多开一行一列是为了让边界情况也能使用该公式。查询任意子矩形的区域和也是通过容斥原理目标区域大矩形dp[x2][y2]减去上方部分dp[x1-1][y2]减去左方部分dp[x2][y1-1]但此时左上角dp[x1-1][y1-1]被多减了一次要加回来故resdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]两个公式本质都是容斥构建时从小到大累加加两块减一块查询时从大到小裁剪减两块加一块一正一反互为逆运算。这样就能在O(m*n)预处理后O(1)求解任意矩阵区域和。