A335.前缀和2 题解

二维前缀和 (此处的 $num$ 指矩阵, $pre$ 指前缀和数组, $ans$ 指询问的回答)

$pre_{i,j}=num_{i,j}+pre_{i-1,j}+pre_{i,j-1}-pre_{i-1,j-1}(i,j>1)$

$ans=pre_{x,y}-pre_{a-1,y}-pre_{x,b-1}+pre_{a-1,b-1}(a,b>1)$

怎么感觉这两个公式这么像(只是符号变了)

Code：

#include <bits/stdc++.h>
using namespace std;
int n,m,q,a,b,x,y,ans;
int num[1005][1005];
int pre[1005][1005];//前缀：prefix
int main(){
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>num[i][j];
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            //套用公式
            pre[i][j]=num[i][j];
            if (i>1) pre[i][j]+=pre[i-1][j];
            if (j>1) pre[i][j]+=pre[i][j-1];
            if (i>1&&j>1) pre[i][j]-=pre[i-1][j-1];
        }
    }
    for (int i=1;i<=q;i++){
        cin>>a>>b>>x>>y;
        //套用公式
        ans=pre[x][y];
        if (a>1) ans-=pre[a-1][y];
        if (b>1) ans-=pre[x][b-1];
        if (a>1&&b>1) ans+=pre[a-1][b-1];
        cout<<ans<<endl;
    }
    return 0;
}