797. 差分

https://www.acwing.com/problem/content/799/

差分模板题
差分就是前缀和的逆运算,重要的时刻确保a[i]=b[0]+b[1]+.....+b[i],这是差分的规定
关键是构造b数组,可以在输入数据的时候b[i]=a[i]-a[i-1]这样构造
要使得一个区间的所有数加c,差分能使得O(N)->O(1)
因为要时刻确保a数组是b数组的前缀和,所以我们更改b数组,就会导致a数组的值发生变化(a数组也是b数组所构成的)
所以我们在b[l]上加上c,那么a[c~n]都会加上c,因为a是由b组成的前缀和嘛
但是我们是要求区间上的数加c,所以要在b[r+1]这里减去c,这样a[r+1~n]的值才不会变
这样的操作只有[L,R]的值会发生改变,满足题意

#include<iostream>
using namespace std;
const int N = 1e5+10;
int num[N];
int b[N];
int n,m,l,r,c;
int main()
{
    cin >> n >> m;
    //输入并构造差分数组
    for(int i=1;i<=n;i++)cin >> num[i],b[i]=num[i]-num[i-1];
    while(m--)
    {
        cin >> l >> r >> c;
        //差分原理
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++)
    {
        //构造差分后的前缀和
        num[i]=b[i]+num[i-1];
    }
    for(int i=1;i<=n;i++)cout << num[i] << " ";
    return 0;
}