题目描述

将一维数组的子区间上每个数加上某个数字，然后重新输出该数组

背模板时需要理清的思路

差分与前缀和是逆运算。差分a[n]用数列的角度来看就是a[n] = S[n] - S[n - 1],注意这个题里存入的a[n]相当于前缀和，b[n]相当于差分数组。因为只有差分数组b[l]加上c,前缀和a[l]才能在l之后的每一项都加上c。即要在a[l]之后的每一项加上c，就要把它视为一个前缀和数组

①存储差分数组（存储是差分的第一步），存储差分数组b[]是insert()完成的。
②恢复为前缀和数组，差分数组在子区间上进行加值计算后要通过公式b[i] += b[i - 1]自身变为前缀和数组。

代码写法上的特点

①insert()在本题中的作用有两个，第一个是用来存储差分数组，可以用insert(i, i, a[i])来存储，其实就是模拟的b[l] = a[l] - a[l - 1]的过程。第二个是用来做差分数组子区间上的加值计算，也就是insert(l, r, c)，即题意想实现的内容。

参考文献

参考y总的代码

C++ 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

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()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; 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];
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;

}