【题解】差分

差分

1. 差分是前缀和的逆运算。前缀和中 b[i] 表示 a[1] 到 a[i] 元素之和，则差分中 b[1] 到 b[i] 元素之和表示 a[i] 。
2. 由于 a 数组是 b 数组的前缀和，所以 b[i] 加 k ，则由 b 数组求出的 a 数组从 a[i] 之后所有元素均会加 k ，所以如果要将 a 数组 [l, r] 区间内每个元素加 k ，那么只需要将 b[l] += k; ，将 b[r + 1] -= k; 即可。

差分 c++ 165ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 5;

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

void insert(int l, int r, int x)
{
    b[l] += x; // a[l, n]均加x
    b[r + 1] -= x; // a[r + 1, n]均减x
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        // 下面写法是从定义出发。也可以写作： insert(i, i, x);
        b[i] = a[i] - a[i - 1];
    }

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

    int ans = 0;
    for (int i = 1; i <= n; i ++ ) 
    {
        ans += b[i];
        printf("%d ", ans);
    }
    return 0;
}