之前我们说过

今天我们来看看二维前缀和

二维前缀和要比一维前缀和难一些

二维前缀和

概念

如图，一个 n*m 的矩阵，

标黑的点是 $i,j)\; ，$那么 $sum(i,j)$（前缀和）为框起的红色部分之和

如果在一矩形中，有一点 (i,j)

$[i][j]$即为矩形左上角的点到 $(i,j)$所有数之和

如何求二维前缀和

思路

我们不难发现， s[i-1][j] 和 s[i][j-i] 有重叠部分（即红色部分）

s[i?1][j]+s[i][j?1]?s[i?1][j?1] （即：红+黄+红+蓝-红） 得出的即为红色部分加上黄色部分加上蓝色部分的和

最后再加上绿色部分 a[i][j] （即这个数本身）

即为 s[i][j]

（你可以理解为小学的容斥原理）

我们可以推出其递推式：

$s[i,j]=$ s[i-1,j]+ s[i,j-1]-s[i-1,j-1]+A[i,j]

代码实现

#include

using namespace std;

int sum[900][900],n,m,a[900][900];

int main()
{
    scanf ("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            scanf ("%d",a[i][j]);//输入
            
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//递推式
        }
    }
    
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
        {
            printf ("%d",sum[i][j]);//输出
        }
        printf ("\n");
    }
    
    return 0;
}

子矩阵求和

二维前缀和的用处就是求子矩阵区间和

对于一个 n*m 的矩阵

如果我们知道其右下点坐标 (i,j)

就可以求出另外3点的坐标：(i-n,j) , (i,j-m) , (i-n,j-m)

然后再来一个容斥就可以求它的区间和

我们有：

? A[x,y]=S[i,j]-S[i-n,j]-S[i,j-m]+S[i-n,j-m]

例题

仍然来看一道题

#include

using namespace std;

int n,m,sum[150][150],s,a,maxn;

int max (const int &a,const int &b)
{
    return a>b?a:b;
}
int min (const int &a,const int &b)
{
    return a