$$差分$$

差分数组可以快速进行区间修改操作。

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。

简单介绍下什么是差分数组：

给定数组 $a_n$ ， $a_n = a[1], a[2], a[3]... ... a[n]$。

我们类似前缀和 $S_n$ 数组构造一个新的数组 $b_n$， $b = b[1], b[2], b[3]... ... b[n]$。

与之不同的是，$b$ 数组表示的是 $a[i] = b[1] + b[2] + b[3] + ... + b[i]$。

即我们新构造出来数组 $b_i$ 的前 $i$ 项的和为原数组的第 $i$ 项，更一般地讲如果一个数组的前 $n$ 项和为另一个数组的第 $n$ 项，则称该数组为另一个数组的差分数组。

考虑如何构造差分 $b$ 数组？

根据定义我们可以发现：

$$b[1] + b[2] + b[3] + ... + b[i - 1] = a[i - 1]$$ $$b[1] + b[2] + b[3] + ... + b[i - 1] + b[i] = a[i] $$

两式相减可得

$$b[i] = a[i] - a[i - 1]$$

那么我们便可通过原数组相邻元素相减的方式得到差分数组的每一项，从而构建出原数组的差分数组。

如何进行区间修改？

我举个简单例子，令 $a_n$ 数组元素全部为零，根据定义可得他的差分数组 $b_n$ 的每一项也为零，此时我们令 $b[1] += 1$，可以发现原数组 $a_n$ 的每一项全部从零变为 $1$。当然如果初始时令 $b[1] -= 1$，根据定义我们仍可得 $a_n$ 的每一项元素全部从零变为 $- 1$ 。

类比可得，令 $b[L] += 1$，$b[R + 1] -= 1$。即可令原数组区间 $[L, R]$ 上的所有元素加 $1$，同理：令 $b[L] += d$，$b[R + 1] -= d$。即可令原数组区间 $[L, R]$ 上的所有元素加 $d$。

修改完毕如何得到原数组？

根据定义：只需跑一遍 for 累加差分数组 $b_n$ 便可得到原数组 $a$。

代码部分

#include<iostream>

using namespace std;

const int N = 500010;
int b[N], a[N];
int n, m;

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

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        insert(i, i, a[i]);
    }

    while (m--)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; ++i) b[i] += b[i - 1];//此时 b[i] == a[i]
    for (int i = 1; i <= n; ++i) printf("%d ", b[i]);

    return 0;
}