差分 | Some Notes

什么是差分，差分与前缀和的关系

差分也是一种优化算法。同时，差分是前缀和的逆运算，也就是说，前缀和也是差分的逆运算。因此，由前缀和数组可以求出差分数组，由差分数组也可以求出前缀和数组。

假设数组 $a$ 是原数组，数组 $b$ 是差分数组，则： $b_{i} = a_{i} - a_{i - 1}$ 。

差分可以用于修改数组的操作。因为假设我需要将 $a_{2}$ $a_{3}$ $a_{4}$ 都加上 $2$ ，此时若使用前缀和则需要再使用递推重新求一遍前缀和，非常耗时。这时便可以使用差分数组。可以发现：

b_{2} + 2 = b_{1} b_{1}, b_{2}, b_{3}, b_{4}, b_{5} b_{5} - 2 = b_{4}

因此，只需修改差分数组中的两个项，然后再通过前缀和是差分的逆运算，即可求出原数组，从而完成数组的修改。

具体例题（模板题）

差分模板题

题目描述

给出 $n (n \leq 1 0^{5})$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ 。
给出一个数字 $m (m \leq 1 0^{5})$ 表示有 $m$ 个修改。
每次询问给出三个整数 $s, e, h$ ，使得 $a_{s}, a_{s + 1}, \dots a_{e}$ 每一个数加上 $h$ 。
最后给出两个数字 $s t a r t, e n d$ 。求出 $\sum_{i = s t a r t}^{e n d} a_{i}$

输出格式

一个整数

输入

输出

提示

第一次修改序列变成 $2, 3, 3, 4, 5$ 。
第二次修改序列变成 $3, 4, 4, 4, 5$ 。
第三次修改序列变成 $3, 4, 4, 5, 6$ 。

$0 \leq a_{i}, h \leq 1 0^{4}$ 。

同上， $b_{s - 1} + h = b_{s}, b_{e + 1} - h = b_{e}$ ，即可使用前缀和倒退回原数组.

代码

#include <cstdio>
using namespace std;

long long a[100002], b[100002], n, m, s, e, h, start, end, sum = 0;
int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
    }
    
    for(int i = 1; i <= n; i++)
    {
        b[i] = a[i] - a[i - 1];
    }
    
    scanf("%lld", &m) ;
    for(int i = 1; i <= m; i++)
    {
        scanf("%lld %lld %lld", &s, &e, &h);
        b[s] += h;
        b[e + 1] -= h;
    }
    for(int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1] + b[i];
    }
    
    scanf("%lld %lld", &start, &end) ;
    for(int i = start; i <= end; i++)
    {
        sum += a[i];
    }
    printf("%lld\n", sum);
    
    return 0;
}