差分

差分定义
$b_1 = a_1$
$b_2 = a_2 - a_1$
$b_3 = a_3 - a_2$
…
$b_n = a_n - a_{n-1}$

$a_n = S_{b_n}$

1.用来实现在[L,r]区间上：$a_n+c$
$$b_l += c$$ $$b_{r+1} -=c$$

2.节省a数组方法：
当L=r时，$a_n$+c可以看作给$a_l$赋值，即不存储a[n]即可求得差分为：
$$a_n=m \Downarrow$$ $$b_n += m $$ $$b_{n+1} -= m $$
(图片中有一处错误)

C++ 代码

#include<iostream>

using namespace std;

const int N=100010;
int b[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        b[i]+=a;
        b[i+1]-=a;
    }
    int l,r,c;
    while(m--){
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    int result=0;
    for(int i=1;i<=n;i++){
        result+=b[i];
        cout<<result<<" ";
    }

    return 0;
}