前缀和

前缀和指数组或序列中每个位置之前的元素总和，可以把它理解为数学上的数列的前n项和，是一种重要的预处理方式，能大大降低查询的时间复杂度。

一维前缀和

原数组：a[1] ，a[2]，a[3]…..a[n]

前缀和：sum[i]=a[1]+a[2]…..a[i]

求前缀和公式：sum[i]=sum[i-1]+a[i] ,s[0]=0;

作用：求原数组[l,r]的和sum

使用原数组计算，则需要从下标l到下标r遍历原数组求和:

sum=a[l]+a[l+1]…..+a[r]；

使用前缀和计算：sum=sum[r]-sum[l-1]

一维前缀和案例

描述

输入n个整数，再输入m个区间，每个区间的起点下标L，终点下标R。对于每个区间，输出n个整数中从下标L到下标R的区间和

输入描述

第一行包括两个整数n和m。（1≤n,m≤100000）

第二行包括n个整数。（1≤整数≤100）接下来有m行，每行包含两个整数L和R，表示区间范围。（0<L≤R≤n）

输出描述

输出有m行，每行一个整数，表示一个区间和。

样例输入

10 3
2 1 3 6 4 20 15 10 4 11
3 7
1 9
5 8

样例输出

48
65
49

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,l,r,a[N],sum[N];//sum[i]表示的状态就是从1到i的区间和 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];//状态转移方程 
    }    
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

差分

一维差分

差分相当于前缀和的逆运算

原数组： a[1]，a[2]…..a[n]

差分数组：d[1]，d[2]…..d[n]

d[n]=a[n]-a[n-1]

求前缀和公式：sum[i]=sum[i-1]+d[i] ;

作用：求原数组[L,R]的数全部加上c ，即a[L]+c，a[L+1]+c, a[R]+c，可以通过操作差分数组进行计算： 即，d[L]+c，d[R+1]-c

（1）原数组a在[1,3]区间加10，得到新数组c：

（2）c[6]对应差分数组d c[i]=d[i]+c[i-1]

（3）a在[1,3]区间加10，对应的差分数组d的变化：d[1]+10，d[4]-10

因此：c[1]=d[1]+a[0] a[3]=d[3]+c[2]

解题过程：

（1）初始化原数组a

（2）求原数组a的差分数组d

（3）求原数组[L,R]的数全部加上c，可以直接操作差分数组d：d[L]+c，d[R+1]-c

（4）根据差分数组d ，求对应的前缀和数组。

一维差分案例

描述

在一个桌子上摆放了 n 个杯子，每个杯子中有一定量的水。小 A 同学负责向杯子中倒水，他总共倒了 k 次，每次会向从第 L 个杯子到第 R 个杯子中添加 P 毫升的水（注意：水只可能增加，不可能减少）。请问小 A 同学倒了 k 次水之后， n 个杯子每个杯子有多少毫升的水。

输入描述

第一行包含两个整数 n 和 k。

第二行包含 n 个整数，表示一开始每个杯子中水的毫升数。

接下来 k 行，每行包含三个整数 L，R，P表示一次操作。

输出描述

共一行，包含 n 个整数，表示最终 n 个杯子每个杯子有多少毫升的水。

样例输入

8 3
1 2 10 8 1 5 1 1
7 8 12
1 8 4
2 3 12

样例输出

5 18 26 12 5 9 17 17

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,l,r,p,a[N],dif[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];//原数组 
        dif[i]=a[i]-a[i-1];//原数组的差分数组 
    }    
    for(int i=1;i<=k;i++){
        cin>>l>>r>>p;
        dif[l]+=p;//操作差分数组 
        dif[r+1]-=p;
    }
    //计算前缀和
    for(int i=1;i<=n;i++){
        a[i]=dif[i]+a[i-1];
        cout<<a[i]<<" ";
    } 
    return 0;
}

总结

• 差分算法可以快速修改序列中某一段连续区间的值。过程如下：
• 在原序列的基础上构造差分数组
• 给区间[L , R] 的元素加上k，那么只需要将差分数组d [ L ] + = k ，d [ R + 1 ] − = k
• 对差分数组计算前缀和来还原出更新之后的序列。