一维差分

题目描述

输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l, r, c, 表示将序列中 [l, r] 之间的每个数加上 c 。
请你输出进行完所有操作后的序列。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式
共一行，包含 n 个整数，表示最终序列。

数学原理

现有原数组 $a_n$
若想将数组下标为 [L, R] 之间的每个数加上 c, 朴素做法需要执行 L - R + 1 次操作。
若利用差分数组只需执行 2 次操作。

原理：
规定任意数组$A_n, $ $A_0 = 0$; R >= L

现通过以下方法构造差分数组 $b_n$
$b_i$ = $a_i$ - $a_{i-1}$
则差分数组 $b_n$ 具有以下性质

$\sum_1^n$ $b_i$ = ($a_1$ - $a_0$) + ($a_2$ - $a_1$) + … + ($a_n$ - $a_{n-1}$) = $a_n$ - $a_0$ = $a_n$

即 $a_n$ = $\sum_1^n$ $b_i$

构造新数组 $b_n^*$
$b_i^*$ = $b_i$ + c (i == L)
$b_i^*$ = $b_i$ (i != L)

当n <= L - 1 时
$a_n^*$ = $\sum_1^n$ $b_i^*$ = $\sum_1^n$ $b_i$ = $a_n$

当n >= L 时
$a_n^*$ = $\sum_1^n$ $b_i^*$ = $\sum_1^{l-1}$ $b_i$ + ($b_l$ + c) + $\sum_{l+1}^n$ $b_i$ = $\sum_1^n$ $b_i$ + c = $a_n$ + c

同理只需要再次构造 $b_n^{**}$
$b_i^{**}$ = $b_i^*$ - c (i == R + 1)
$b_i^{**}$ = $b_i^*$ (i != R + 1)

当 n <= L - 1 时
$a_n^{**}$ = $\sum_1^n$ $b_i^{**}$ = $\sum_1^n$ $b_i^*$ = $a_n$

当 L <= n <= R 时
$a_n^{**}$ = $\sum_1^n$ $b_i^{**}$ = $\sum_1^n$ $b_i^*$ = $a_n$ + c

当n >= R + 1 时
$a_n^{**}$ = $\sum_1^n$ $b_i^{**}$ = $\sum_1^{r}$ $b_i^*$ + ($b_{r+1}^*$ - c) + $\sum_{r+2}^n$ $b_i^*$ = $\sum_1^n$ $b_i^*$ - c = $a_n^*$ - c = $a_n$ + c - c = $a_n$

则 $a_n^{**}$ 为我们的目标数组，且只需要对差分数组 $b_n$ 进行以下两次操作得到
$b_{l}$ = $b_{l}$ + c
$b_{r+1}$ = $b_{r+1}$ - c

注意：
差分只能用于一次性处理完所有偏移指令，再还原。
如果是偏移和还原交错进行，就不是单独一个差分序列能高效解决的问题了。

代码实现

参考文献

https://www.acwing.com/solution/content/223661/

C++ 代码

#include <iostream>
using namespace std;
#define int long long

const int N = 1e5 + 10;
int a[N], d[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    a[0] = 0; d[0] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%lld",&a[i]);
        d[i] = a[i] - a[i-1];
    }

    while(m--)
    {
        int l, r, c;
        scanf("%lld%lld%lld",&l,&r,&c);
        d[l] += c;
        d[r+1] -= c;
    }
    int sum = 0;
    for(int i = 1; i <= n; ++ i)
    {
        sum += d[i];
        printf("%lld ",sum);
    }
    return 0;
}