AcWing 797. 差分

原题链接：https://www.acwing.com/problem/content/description/799/

所谓的差分，是对于一个数组，定义一个数组，使得是的前缀和数组。即： 为了满足这个条件，我们可以构造这样一个数组： 所以差分又是前缀和的逆运算。通过差分数组，我们可以方便地为中的任意一段区间加上或者减去一个数，其时间复杂度为。

#include <iostream>

#define N 100005

int a[N], b[N];

int main() {
    
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    
    // 构造差分数组
    // b[0] = a[1]
    // b[1] + b[0] = a[2]
    // b[2] + b[1] + b[0] = a[3];
    // ...
    // b[i] = a[i+1] - a[i],
    b[0] = a[1];
    for (int i = 1; i < n; ++i) b[i] = a[i+1] - a[i];
    
    // 由于a[]是b[]的前缀和
    // a[1,3]之间加上c
    // 所以b[0]+c后，a[1,n]都会+c
    // b[3]-c后，a[4,n]都会-c
    // 最终的效果就是a[1,3]之间加c
    int l, r, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &l, &r, &c);
        b[l-1] += c; b[r] -= c;
    }
    // 输出最终结果
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += b[i];
        printf("%d ", sum);
    }
    
    return 0;
}