一维差分

定义

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令

$$b_i=\begin{cases}a_i-a_{i-1}\,&i \in[2,n] \\ a_1\,&i=1\end{cases} $$

其中 $\in$ 是属于的意思，$i\in [2, n]$ 其含义为 $i$ 处于 $2\sim n$ 之间的时候。

$b_i=a_i-a_{i-1}$ 可得 $a_i=a_{i-1}+b_i$

例如：

• $b_1=a_1-a_0=a_1-0=a_1$
• $b_2=a_2-a_1$
• $b_3=a_3-a_2$

性质

• $a_i$ 的值就是 $b_i$ 的前缀和，即 $a_n=b_1+b_2+\cdots+b_n$。

证明：

等号右边利用差分的定义可以写成

$$a_1+(a_2-a_1)+(a_3-a_2)+\cdots+(a_n-a_{n-1})$$

化简后就剩一个 $a_n$。

$$\begin{aligned} a_i&=b_1+b_2+\cdots+b_i\\ &=a_1+(a_2-a_1)+\cdots+(a_i-a_{i-1})\\ &=a_i \end{aligned} $$

例如：

• $a_1=b_1$
• $a_2=b_1+b_2=a_1+(a_2-a_1)$
• $a_3=b_1+b_2+b_3=a_1+(a_2-a_1)+(a_3-a_2)$
• 计算 $a_i$ 的前缀和

$$sum=\sum\limits_{i=1}^na_i=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i}b_j=\sum\limits_{i=1}^n(n-i+1)b_i $$

其中 $\sum$ 为求和符号，例如 $\sum\limits_{i=1}^n a_i$ 的含义就是 $a_1+a_2+\cdots+a_n$。

证明：

$$\begin{aligned} &\ \ \ \ \ a_1+a_2+\cdots+a_n\\ &=b_1+(b_1+b_2)+\cdots+(b_1+b_2+\cdots+b_n)\\ &=n\times b_1+(n-1)\times b_2+\cdots+1\times b_n\\ &=\sum\limits_{i=1}^n(n-i+1)b_i \end{aligned} $$

• 给一个序列某一段 连续区间 内的所有数字都增加一个 $c$。（$c$ 正负无所谓）

暴力写法如下：

while (q--)
{
    cin >> l >> r >> c;
    for (int j = l; j <= r; j++)
        a[j] += c;
}

使用差分数组可以在 $O(1)$ 的时间内修改。只需要执行

b[l] += c, b[r + 1] -= c

证明：

1. 当我们对 $b_l+c$ 以后，首先易得出 $b_1\sim b_{l-1}$ 的值并未改变。所以 $a_1\sim a_{l-1}$ 的值也不变。

根据性质 $1$，原数组的值就是差分数组的前缀和可得该结论。

例如 $a_{l-1}=b_1+b_2+\cdots+b_{l-1}$ 由于 $b_1\sim b_{l-1}$ 没变，所以 $a_{l-1}$ 也没变。

进一步可得 $a_1\sim a_{l-1}$ 的值都不变。

2. 当执行 $b_l+c$ 以后，可得 $a_l\sim a_n$ 都加了 $c$

举例：

• $a_l = b_1 + b_2 + \cdots + \mathbf{b_l}$ 由于 $b_l + c$，因此 $a_l + c$
• $a_{l+1} = b_1 + b_2 + \cdots + \mathbf{b_l}+b_{l+1}$ 由于 $b_l + c$，因此 $a_{l+1} + c$
• $a_n = b_1 + b_2 + \cdots + \mathbf{b_l}+\cdots+b_n$ 由于 $b_l + c$，因此 $a_n + c$*

3. 当执行 $b_{r+1}-c$ 以后，可得 $a_{r+1}\sim a_n$ 都减了 $c$

• $a_{r + 1} = b_1 + b_2 +\cdots + \mathbf{b_l} + \cdots+ \mathbf{b_{r + 1}}$

由于 $b_l + c$，$b_{r + 1} - c$，因此正负抵消 $a_{r + 1}$ 不变

• $a_{n} = b_1 + b_2 +\cdots + \mathbf{b_l} + \cdots+ \mathbf{b_{r + 1}}+\cdots+b_n$

由于 $b_l + c$，$b_{r + 1} - c$，因此正负抵消 $a_{n}$ 不变

注意事项

• 注意是给一段连续区间内的所有数字都去增加，而不是挑选若干个数字进行修改。
• 注意使用的时候，保证 $l\leq r$。

做题步骤

• 先预处理差分数组，通过 b[i] = a[i] - a[i - 1] 求出。
• 通过差分的修改操作，修改数组 b
• 对区间修改操作转化到差分数组的修改上。
• 对 b 数组求前缀和得到原数组的值。