C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

一个经典的例题：

暴力当然直接TLE

//这段代码是能拿50分的，大规模会有超时问题
//没有很好的利用前缀和
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a;
    for(int i=0;i<n;i++){
        int t;cin>>t;
        a.push_back(t);
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int l,r,t=0;
        cin>>l>>r;
        for(int j=l-1;j<=r-1;j++)t+=a[j];
        cout<<t<<endl;
    }
    return 0;
}

将上面代码的加起来的过程给优化一下，在输入阶段就将数组改写成前缀和的形式，输出的时候只要s[r]-s[l-1]就可以了

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a;a.push_back(0);
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        a.push_back(t+a[i-1]);
    }
    int m;cin>>m;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        cout<<a[r]-a[l-1]<<endl;
    }
    return 0;
}

从一维扩展到二维，思考方式就多了

一个是基于容斥原理，什么是容斥原理？这涉及到数学上集合的概念了。先看下面的图：

现在给了A,B,C三个集合的元素数量，要求你求出至少在一个元素的数量，他不能是直接把三个集合的元素加起来，必须得把重复的元素给扣掉，计算这个数量的过程就是容斥原理。

现在回到二维前缀和的部分，给定大小为 m *n 的二维数组 A，要求出其前缀和 S。那么，S 同样是大小为 m* n 的二维数组，且

类比一维的情形，S{i,j} 应该可以基于 S{i-1,j} 或 S{i,j-1} 计算，从而避免重复计算前面若干项的和。但是，如果直接将 S{i-1,j} 和 S{i,j-1} 相加，再加上 A{i,j}，会导致重复计算 S{i-1,j-1} 这一重叠部分的前缀和，所以还需要再将这部分减掉。这就符合了容斥原理。由此得到如下递推关系：

实现时，直接遍历 (i,j) 求和即可。

同样的道理，在已经预处理出二位前缀和后，要查询左上角为 (i[1],j[1])、右下角为 (i[2],j[2]) 的子矩阵的和，可以计算

这可以在 O(1) 时间内完成。

在二维的情形，以上算法的时间复杂度可以简单认为是 O(mn)，即与给定数组的大小成线性关系。但是，当维度 k 增大时，由于容斥原理涉及的项数以指数级的速度增长，时间复杂度会成为 O(2^kN)，这里 k 是数组维度，而 N 是给定数组大小。因此，该算法不再适用。

接下来是差分：
差分的定义：在多张图画中，主体结构不变，展现其他较小变化的多张图片，可称其互为差分。

在算法中，他是一种和前缀和相对的策略

这里的a[i]即数组中每个元素

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

例题：

思路

这题明显就是差分

根据差分数组的定义： d[i]=a[i]-a[i-1]，可以发现，在d[x]上加上z,会让后面的学生全部加上z。↓

但这是把后面全部都加了，还要减掉一节，所以↓

把两个综合起来就是↓

所以每一次变化只要把d[x]+z,d[y+1]-z就好了。

因为 d[i]=a[i]-a[i-1]

所以 a[i-1]+d[i]=a[i]

最后再根据 a[i-1]+d[i]=a[i]输出每一个同学的分数

题解：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,p;
    cin>>n>>p;
    vector<int>a(n+1,0),d(n+1,0);//动态分配内存的数组
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];//差分
    }
    int x,y,z;
    for(int i=0;i<p;i++){
        cin>>x>>y>>z;
        d[x]+=z,d[y+1]-=z;
    }
    int min=300;
    //找出分数最少的学生
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+d[i];
        if(min>a[i])min=a[i];
    }
    //经过上面的操作，将时间复杂度给干到O(n)了
    cout<<min<<endl;
    return 0;
}