2025-01-23前缀和

前缀和

情景

求区间[l,r]之间所有元素的和。

主要内容

一维前缀和

二维前缀和

模板题

https://blog.csdn.net/qq_44426403/article/details/134255195

一维前缀和

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N=1e5+5;
int sum[N];

void work(){
    cin>>n>>m;
    int pre=0,a;
    for(int i=1;i<=n;i++){
        cin>>a;
        sum[i]=a+pre;
        pre=sum[i];
    }

    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
}

int main(){
    work();
    return 0;
}

二维前缀和

#include<bits/stdc++.h>
using namespace std;

int n,m,q;
const int N=1005;
int sum[N][N];


void work(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int a;
            cin>>a;
            sum[i][j]=a+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
            
    while(q--){
        int x1,y1,x2,y2;//左上和右下
        cin>>x1>>y1>>x2>>y2;

        cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
    }
}

int main(){
    work();
    return 0;
}