算法概述:

• 前缀和是一种预处理，在之后的计算中直接应用前面已经算出的结果。

• 前缀和分为一维前缀和 与 二维前缀和.

• 一个一维数组的前缀和可以理解为数学上的数列的前n项和.(定义对于一个数组a的前缀和数组sum，sum[i] = a[1]+a[2]+…+a[i]);

• 一个二维数组的前缀和与一维数组类似,设s[i][j]表示所有a[i’][j’]的和(1≤i’≤i,1≤j’≤j);

• 前缀和的用途:一般用来求区间和
  对于一维情况，现在给出一个数列a，要求你回答m次询问，每次询问下标j到k的和。朴素的做法显然是对于每次询问都执行一次相加操作，然后输出结果。这样做是正确的，但是当m过大时就会导致计算次数过多而有可能超时。

795. 前缀和
朴素做法:

#include<iostream>
using namespace std;
const int N = 100010;
int main()
{
    int n,m,l,r;
    int a[N];
    cin>>n>>m;
    for(int i=0;i<n;++i)
        cin>>a[i];

    while(m--)
    {
        long long sum=0;
        cin>>l>>r;
        for(int i=l-1;i<r;++i)
            sum+=a[i];

        cout<<sum<<endl;
    }
    return 0;
}
时间复杂度O(n*m);
//果然TLE!

前缀和做法:

#include<iostream>
using namespace std;
const int N = 100010; 
int main()
{
    int n,m,l,r;
    int a[N];
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>a[i];

    long long sum[N];
    sum[0]=a[0];
    for(int i=1;i<n;++i)
        sum[i]=sum[i-1]+a[i];

    while(m--)
    {
        cin>>l>>r;
        cout<<sum[r-1]-sum[l-2]<<endl;//因为下标是从0开始的，所以第l和r个数对应数组的下标是l-1,r-1.
    }
    return 0;
}
时间复杂度O(n+m);

按照上面做法,运行能AC，但是存在问题，当输入1 2的时候,是算的sum[1]-sum[-1]的值!!!!其实只要输入1 r,输出的都是sum[r-1]-sum[-1];但是为什么能AC呢，那是因为sum[-1]的值为0，这样肯定不行啊，所以要进行修改:

规定:

• 在读入数组的时候下标从1开始！
• 前缀和数组下标也是要从1开始,并且要将前缀和数组声明成全局变量.

#include<iostream>
using namespace std;
const int N = 100010; 
int a[N];
long long sum[N];
int main()
{
    int n,m,l,r;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];

    for(int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i];

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

所以下面递增三元数组那个题也有问题

习题:

一维前缀和:

1.AcWing 1236. 递增三元组(第九届蓝桥杯省赛C++B组)

读完题第一反应就是暴力，没细想数据范围

#include<iostream>
using namespace std;
const int N = 100010;
int main()
{
    int n;
    int a[N],b[N],c[N];
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i) cin>>b[i];
    for(int i=0;i<n;++i) cin>>c[i];

    long long cnt=0;
    //cout<<cnt<<endl;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j){
            if(a[i]<b[j])
                for(int k=0;k<n;++k)
                    if(a[i]<b[j]&&b[j]<c[k]) cnt++;

        }                
    cout<<cnt;
    return 0;
}

果不其然，TLE了，只通过了6/12个数据
下面就在想怎么优化:首先对每个数组进行从小到大排序，排完序以后，对于遍历a数组时，如果a[i]>b[n-1],那么对于这个i肯定没有满足的情况，对于遍历b数组时，如果b[j]>k[n-1],那么对于这个j肯定没有满足的情况.

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int main()
{
    int n;
    int a[N],b[N],c[N];
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i) cin>>b[i];
    for(int i=0;i<n;++i) cin>>c[i];

    sort(a,a+n); sort(b,b+n); sort(c,c+n);

    long long cnt=0;
    int i,j,k;
    for(i=0;i<n;++i)
        if(a[i]<b[n-1])//如果第一行的某一元素大于第二行最后一个元素(排序后最后一个元素也是最大元素)，那肯定不满足
            for(j=0;j<n;++j)
                if(a[i]<b[j])
                    for(k=0;k<n;++k)
                        if(b[j]>c[n-1]) break;
                        else{
                            if(a[i]<b[j]&&b[j]<c[k]) cnt++;
                        }
    cout<<cnt;
    return 0;
}

依旧TLE，还是只通过了6/12个数据，说明压根就不能用这三重for循环.
于是看了y总的思路:

下面先说一下前缀和的代码:

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N],b[N],c[N];
int as[N];//as[i]表示在a[]中有多少个数小于b[i]
int cs[N];//cs[i]表示在c[]中有多少个数大于b[i]
int cnt[N],s[N];

long long sum=0;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i],a[i]++;
    for(int i=0;i<n;++i) cin>>b[i],b[i]++;
    for(int i=0;i<n;++i) cin>>c[i],c[i]++;

    //求as[]
    for(int i=0;i<n;++i) cnt[a[i]]++;
    for(int i=1;i<N;++i) s[i]=s[i-1]+cnt[i]; //求cnt[]的前缀和
    for(int i=0;i<n;++i) as[i]=s[b[i]-1]; //因为要求的是小于，所以这个地方要-1

    //求cs[]
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    for(int i=0;i<n;++i) cnt[c[i]]++;
    for(int i=1;i<N;++i) s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;++i) cs[i]=s[N-1]-s[b[i]];

    LL res = 0;
    //枚举每个b[i];
    for(int i = 0;i<n;++i) res+=(LL)as[i]*cs[i];

    cout<<res;

    return 0;
}

刚开始没想明白输入的时候为什么要+1，其实是把之前的0放到1的位置上了，在求前缀和的时候不用在for前写一句s[0]=cnt[0],如果不+1，那么代码如下:(必须要加一，下边不+1的想法是错误的！！！！！)

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N],b[N],c[N];
int as[N];//as[i]表示在a[]中有多少个数小于b[i]
int cs[N];//cs[i]表示在c[]中有多少个数大于b[i]
int cnt[N],s[N];

long long sum=0;

int main()
{
    cin>>n;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i) cin>>b[i];
    for(int i=0;i<n;++i) cin>>c[i];

    //求as[]
    for(int i=0;i<n;++i) cnt[a[i]]++;
    s[0]=cnt[0];
    for(int i=1;i<N;++i) s[i]=s[i-1]+cnt[i]; //求cnt[]的前缀和
    for(int i=0;i<n;++i) as[i]=s[b[i]-1]; //因为要求的是小于，所以这个地方要-1

    //求cs[]
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    for(int i=0;i<n;++i) cnt[c[i]]++;
    s[0]=cnt[0];
    for(int i=1;i<N;++i) s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;++i) cs[i]=s[N-1]-s[b[i]];

    LL res = 0;
    //枚举每个b[i];
    for(int i = 0;i<n;++i) res+=(LL)as[i]*cs[i];

    cout<<res;

    return 0;
}

2. AcWing 1230. K倍区间(第八届蓝桥杯省赛C++B组)

首先想到的是暴力算法，双重for循环来遍历子串，双重for循环中再嵌套一个for来求(i,j)区间的和

#include<iostream>
using namespace std;
const int N = 100010;

int a[N];
int s[N];
int b[N];
int main()
{
    int n,k,sum,cnt=0;
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>a[i];//读入数组


    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j){
            sum=0;
            for(k=i;k<=j;++k)
                sum+=a[k];
            if(sum%k==0) cnt++;
        }

    cout<<cnt;
    return 0;
}

时间复杂度:O(n的三次方),不用想，肯定TLE;下面想想怎么进行优化:
求(i,j)的时候可以用前缀和，这样时间复杂度就成了O(n的二次方).但还是TLE.

#include<iostream>
using namespace std;
const int N = 100010;

int a[N];
int s[N];
int main()
{
    int n,k,sum=0;
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>a[i];//读入数组

    for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i];//求前缀和

    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            if((s[j]-s[i-1])%k==0)
                sum++;

    cout<<sum;
    return 0;
}

因为此题的数据范围是(1,100000),那么就表明这个题时间复杂度应为O(n)或者O(nlongn),即最多只能用一个for(),不能进行循环嵌套.
很明显，下面就要优化双指针求子列了:

二维前缀和: