前缀和

CR__7 · 2021-09-13 20:26:41 · 个人记录

一维前缀和

1. si=a1+a2+a3+......+ai

2.sum(L,R)=al+al+1+......+ar=s[r]-s[l-1]

步骤

1.预处理前缀和数组

2.用公式求区间和

代码

#include<iostream>
#include<cstdio>

const int N=100100;

int a[N],s[N];
int n,r;
int main()
{
    scanf("%d%d",&n,&r);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];
    for(int i=1;i<=r;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d",s[r]-s[l-1]);
    }
    return 0;
}

二维前缀和

公式：

1、求前缀和：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

2、算子矩阵和：s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y2-1]

代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int N=1010;
int a[N][N],sum[N][N],q;
int main()
{
    int n,m;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
    while(q--)
    {
        int x,y,xx,yy;
        scanf("%d%d%d%d",&x,&y,&xx,&yy);
        cout<<sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1]+sum[x-1][y-1]<<endl;
    }
    return 0;
}

例题

p1719最大加权矩阵