前缀和

前缀和是一种很重要的思想其实这个思想很简单

就是一次预处理把原来O(N*M)的复杂度降到O(N+M)

∑_{a[i]+...+a[j]}=sum[j]-sum[i-1];

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)) (ch=='-')?(f=-1,ch=getchar()):ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
int n;
const int N=1<<20;
int a[N],sum[N];
signed main(){
    memset(sum,0,sizeof(sum));//先清空数组
    n=read();
    for(register int i=1;i<=n;i++) a[i]=read();//读入
    for(register int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];//前缀和
}

那么区间的数值查询该怎么做呢

假设有m次查询

for(register int i=1;i<=m;i++) {
        int x=read(),y=read();
        ans=sum[y]-sum[x-1];
    }

ans=∑_a[x]+...a[y];

如上所述

∑_a[x]+...a[y]=sum[y]-sum[x-1];

想想看为什么要 -1 而不是 sum[y]-sum[x]

举个例子：

n=5

i	1	2	3	4	5
a[i]	5	3	4	2	1
sum[i]	5	8	12	14	15

看例子自己体会吧...（我太菜了讲不明白）

接下来来几道例题

例1

Problem

给出一个含有

Input Data

第一行为一个整数

Output Data

每组数据输出

#include<bits/stdc++.h>
#define ULL unsigned long long
#define MAXN 100000+5
#define f(i,j,n) for(register int i=j;i<=n;i++)
using namespace std;
ULL T,a[MAXN],n,m;
void solve(int T) {
    while(T--) {
        memset(a,0,sizeof(a));
        cin>>n>>m;
        f(i,1,n) {
            int x;
            cin>>x;
            a[i]=a[i-1]+x;
        }
        f(i,1,m) {
            int l,r;
            cin>>l>>r;
            cout<<a[r]-a[l-1]<<endl;
        }
    }
}
int main() {

    cin>>T;
    solve(T);
    return 0;
}

例1

例2

Problem

给定

Input Data

第一行，2个整数n和m，范围在

Output Data

一个整数，表示最小值。

这题是通过预处理之后再进行枚举（也是前缀和的通常做法）

#include<bits/stdc++.h>
#define ULL unsigned long long
#define MAXN 100000+5
#define f(i,j,n) for(register int i=j;i<=n;i++)
#define INF 2147483647
using namespace std;
ULL a[MAXN],n,m,MIN=INF;
void solve(int T) {
    while(T--) {
        memset(a,0,sizeof(a));
        cin>>n>>m;
        f(i,1,n) {
            int x;
            cin>>x;
            a[i]=a[i-1]+x;
        }
        f(i,m,n) MIN=min(MIN,a[i]-a[i-m]);
        cout<<MIN<<endl;
    }
}
int main() {
    solve(1);
    return 0;
}

例2

例3

在一个

Input Data

第一行为两个整数

Output Data

一个整数，最大正方形的边长

#include<bits/stdc++.h>
#define ULL unsigned long long
#define MAXN 100+5
#define f(i,j,n) for(register int i=j;i<=n;i++)
using namespace std;
ULL T,a[MAXN][MAXN],n,m;
int q(int i,int j,int k,int l) {
    f(p,i,j)
    f(q,k,l)
    if(a[p][q]==0) return 0;
    return min(j-i+1,l-k+1);
}
void solve(int T) {
    int ans=0;
    while(T--) {
        memset(a,0,sizeof(a));
        cin>>n>>m;
        f(i,1,n)
        f(j,1,m) {
            int x;
            cin>>x;
            a[i][j]=x;
        }
        f(i,1,n)
        f(j,i,n)
        f(k,1,m)
        f(l,k,m)
        ans=max(ans,q(i,j,k,l));
        cout<<ans<<endl;
    }
}
int main() {
    solve(1);
    return 0;
}

例3

例4

拓展（二维前缀和）

#include<bits/stdc++.h>
#define f(i,j,n) for(register int i=j;i<=n;i++)
using namespace std;
const int N=100;
int n,m;
int a[N][N];
int main() {
    scanf("%d",&n,&m);
    f(i,1,n)
    f(j,1,m) {
        int x;
        scanf("%d", &x);
        a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    }
    int x1, y1, x2, y2;
    while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)) printf("%d
",a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]);
    return 0;
}

二维前缀和

$B Z O J 1218$

Problem

一种新型的激光炸弹，可以摧毁一个边长为

Input Data

输入文件的第一行为正整数

Output Data

输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过

#include <bits/stdc++.h>
#define f(i,j,n) for(register int i=j;i<=n;i++)
#define M 5010
using namespace std;
int n,r,ans,sum[M][M];
int main() {
    int x,y,z;
    cin>>n>>r;
    f(i,1,n) scanf("%d%d%d",&x,&y,&z),sum[x+1][y+1]+=z;
    f(i,1,5000) f(j,1,5000) sum[i][j]+=sum[i-1][j];
    f(i,1,5000) f(j,1,5000) sum[i][j]+=sum[i][j-1];
    f(i,r,5000) f(j,r,5000) ans=max(ans,sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]);
    cout<<ans<<endl;
    return 0;
}

例4

（代码都是好久以前写的了码风可能不太好见谅）

不存在十全十美的文章如同不存在彻头彻尾的绝望