一维差分

差分定义：就是一个数组中相邻的两个数的差值所组成的新数组！

b[1] = a[1] - a[0]  =>  a[1] = b[1]
b[2] = a[2] - a[1]  =>  a[2] = b[2] + a[1] = b[2] + b[1]
b[3] = a[3] - a[2]  =>  a[3] = b[3] + a[2] = b[3] + b[2] + b[1] 
...

so: a[i] = b[i] + b[i - 1] + ... + b[1];

可以说：$b[i]$ 是 $a[i]$ 的差分数组；$a[i]$ 是 $b[i]$ 前缀和。

所以说： 原数组的数 是 差分数组的前缀和

差分核心操作！将a[l] ~ a[r] 全部加上 c，等同于 b[l] += c,b[r + 1] -= c

小推导：

    b[l] = a[l]     - a[l - 1]  =>     b[l] = (a[l]+c) - a[l - 1]     => b[l] + c
b[l + 1] = a[l + 1] - a[l]      => b[l + 1] = (a[l + 1]+c) - (a[l]+c)    还是 b[l + 1]
...

    b[r] = a[r]     - a[r - 1]  =>     b[r] = (a[r]+c) - (a[r - 1]+c)    还是 b[r]
b[r + 1] = a[r + 1] - a[r]      => b[r + 1] = a[r + 1] - (a[r] + c)   => b[r + 1] - c

所以差分数组维护区间和 就是

b[l] += c;
b[r + 1] -= c

然后记得：差分数组离线求完之后，再算出差分数组的前缀和，才是改变后的数组啦！！

code:

#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        // 初始化差分数组
        b[i] = a[i] - a[i - 1];   // insert(i, i, a[i]);
    }

    while(m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

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

    for (int i = 1; i <= n; i ++ ) cout << a[i] << ' ';
    return 0;
}