差分

一维差分概述

$a[N]$是原数组即前缀和数组, $a[N]$是$b[N]$的前缀和数组, 则称 $b[N]$是$a[N]$的差分数组, $b[i] = a[i] - a[i - 1]$
前缀和与差分是一组互逆运算

差分的作用

当我们想对，原数组(前缀和数组)的一段区间加上一个常数$c$时，是$O(N)$的，若是操作次数很多，那么时间会很长。
利用差分数组，我们可以通过$O(1)$的时间完成需求

差分操作与差分构造

要在区间$l$ ~ $r$间的原数组每个数$ + c $，那么需要差分操作操作
本题中a[N]是前缀和数组, b[N]是差分数组
操作如下:
$b[l] += c, b[r + 1] -= c $

差分的构造:
1. 利用定义$ b[i] = a[i] - a[i - 1] $
2. 我们可以想象开始前缀和数组均为$0$,每次输入一个该数组中的数字，当做在区间$i$ ~ $i$间插入这个数字，也就是说，初始化操作可以通过插入来完成

一个习惯

这四道题， y总习惯最后在数组上操作达到答案数组
本题就是在差分数组上操作得到原数组

代码模板

一维差分
B[i] = a[i] - a[i - 1]
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

代码

#include <iostream>

using namespace std;

const int N = 100010;

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;
}