一维和二维前缀和模板

在这里插入代码
#一维前缀和
1、首先建立a[N]和s[N]//s[N]是前缀和数组
2、预处理前缀和数组，使得s[i]=s[i-1]+a[i];
3、求[l,r]范围的前缀和，就是s[r]-s[l-1]
4、最重要的是数组从1开始，为了方便处理
##模板
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N=100010;

int a[N],s[N];

int main()
{
    int n,m;
    ios::sync_with_stdio(false);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
}
#二维前缀和
1、s[i][j]怎么求？
公式s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
2、那么怎么求子矩阵的和呢？
就是s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][x2-1]
##模板
#include<iostream>

using namespace std;

const int N=1010;
int a[N][N],s[N][N];

int main()
{
    int n,m,q;
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>a[i][j];
    
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    
    
    
}