第5课：差分

频繁修改任意区间的值。可将枚举算法二重循环的时间复杂度，降低到一重循环的级别。

（1）首先将原数组a转换为差分数组b。转换公式为：b[i] = a[i] -a[i-1];
（2）对原数组a中下标l到r之间所有元素加上c，转换为，对差分数组b中下标l的元素加上c，对下标r+1的元素减去c，即：b[l] + c; b[r+1] – c; 
（3）对差分数组b，进行前缀和操作，得到修改后的原数组a，即：a[i] = a[i-1] +b[i];

int a[100010], b[100010];
int main()
{
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= n; i++)
    {
        cin>>a[i];
        b[i] = a[i] - a[i - 1];      //构建差分数组
    }
    int l, r, c;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>c;
        b[l] += c;     //将序列中[l, r]之间的每个数都加上c
        b[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] = b[i] + a[i - 1];    //前缀和运算
        cout<<a[i]<<" ";
    }
    return 0;
}