前缀和详解

· · 个人记录

前缀和是一种算法

不算精妙吧

有点暴力

一维前缀和

概念

对于一个一维数组（a）来说，它的前缀数列是这样的

S[i]=\sum\limits_{j=1}^iA[j]

可以通过递推求出

s[i]=s[i-1]+a[i] 
int a[10];
int sum[10];//前缀和数组
sum[1]=a[1];
sum[2]=a[1]+a[2];
sum[3]=a[1]+a[2]+a[3];
sum[4]=a[1]+a[2]+a[3]+a[4];
......

以此类推

用法

可以很快的求子区间的和

表现为前缀和相减的形式

sum(l,r)=$ $\sum\limits_{i=l}^rA[j]=S[r]-S[l-1]

比如说求 a[2]+a[3]

sum[3]=a[1]+a[2]+a[3];
sum[1]=a[1];
a[2]+a[3]=+a[1]+a[2]+a[3]-a[1];
a[2]+a[3]=sum[3]-sum[1];

像酱紫就可以很方便的求出子区间的和

例题

来看一道题

首先想到暴力，然鹅根本不可能直接枚举（TLE）

然后打开标签

会发现有前缀和三个字 （恍然大悟）

前缀和可以用来干什么？

求子区间和

于是题意就明了了

预处理前缀和，然后暴力枚举

Code 
#include<cstdio>
using namespace std;
int sum[2100000],n;
int main(){
    scanf ("%d",&n);
    for (int i=1;i<=n;++i){
        sum[i]=sum[i-1]+i;
    }
    for (int i=1;i<n;++i){
        for (int j=i+1;j<n;++j){
            if (sum[j]-sum[i]==n){
                printf ("%d %d\n",i+1,j);
            }
        }
    }
    return 0;
}

然后我们惊奇的发现T了

考虑优化

当sum[j]-sum[i]>n时，所计算的都无用，因为我们要求的是等于n的数

于是加上优化

AC code 
#include<cstdio>
using namespace std;
int sum[2100000],n;
int main(){
    scanf ("%d",&n);
    for (int i=1;i<=n;++i){
        sum[i]=sum[i-1]+i;
    }
    for (int i=1;i<n;++i){
        for (int j=i+1;j<n;++j){
            if (sum[j]-sum[i]>n){
                break;
            }
            if (sum[j]-sum[i]==n){
                printf ("%d %d\n",i+1,j);
            }
        }
    }
    return 0;
}

二维前缀和

要比一维前缀和难一些

概念

如图，有一个 n*m的矩阵，标黑的点是 (i,j),那么sum(i,j)（前缀和）为框起的红色部分之和

如果在一矩形中，有一点(i,j)

**同样是矩阵** 即 $s[i,j]=\sum\limits_{x=1}^i\sum\limits_{y=1}^jA[x,y]

如何求二维前缀和

思路

观察可知，s[i-1][j]和s[i][j-1]有重叠部分（红色部分）

再加上蓝色部分$A[i][j]$(这个数本身) 即为$s[i][j]

其实是容斥原理

结合递推式理解

s[i,j]=$ $s[i-1,j]+$ $s[i,j-1]$ $-s[i-1,j-1]+A[i,j]

这样就可以通过递推的方式求出每一项的前缀和

代码

#include<iostream>
using namespace std;
int sum[900][900],n,m,A[900][900];
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            cin>>A[i][j];//输入
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j];//递推式
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            cout<<sum[i][j]<<" ";//输出
        }
        cout<<endl;
    }
    return 0;
}

求子矩阵的和

二维前缀和的用处就是求子区间和

对于一个n*m的矩阵

知道它的右下坐标i,j

可以求它的区间和

我们有

\sum\limits_{x=i-n+1}^i$ $\sum\limits_{y=j-m+1}^j$ $A[x,y]=S[i,j]-S[i-n,j]-S[i,j-m]+S[i-n,j-m]

例题

题目传送门

不会dp，所以暴力

用二维前缀和预处理0的数量

枚举(i,j)

再加一层循环枚举正方形边长r

此时算出子矩阵0的个数

若为0 ，更新答案maxn

优化

若枚举r时0的个数已经不为0，则此时再往下枚举所有正方形都包含0

可以直接break

AC code 
#include<iostream>
using namespace std;
int n,m,s[150][150],v,x,maxn;
int main (){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            cin>>x;
            if (x==0) x=1;
            else if (x==1) x=0;
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;//前缀和 
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            for (int r=1;r<=min(i,j);++r){//枚举正方形边长r 
                v=s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r];//子区间（子矩阵） 0的个数 
                if (v!=0) break;//优化 
                if (v==0) maxn=max (r,maxn);//更新答案 
            }
        }
    }
    cout<<maxn;
}
End