概念
数列 $a$，$b$ 满足以下条件：
$$ \begin{align*} b_1 &= a_1\\ b_2 &= a_2 - a_1\\ &\vdots\\ b_n &= a_n - a_{n-1} \end{align*} $$故有：
$$ \begin{align*} a_1 &= b_1\\ a_2 &= b_1 + b_2\\ &\vdots\\ a_n &= b_1 + b_2 + \cdots + b_n \end{align*} $$其中称 $b$ 为 $a$ 的差分（Difference Array），$a$ 为 $b$ 的前缀和（Prefix Sum Array）。两者为一组逆运算。
用法
差分数列的一个重要用途，是用来在原数列上实现快速的区间更新。例如现在要给数列 $a$ 在区间 $[l,r]$ 上的每个数加 $c$ ，最简单的办法是遍历该区间并修改每个数， 时间复杂度为 $O\left(n\right)$；而使用差分数列只需
$$ \begin{align*} b_l \mathrel{+}= c\\ b_{r+1} \mathrel{-}= c \end{align*} $$即可，此时数列 $b$ 为：
$$ \begin{align*} b_1 &= a_1 \\ b_2 &= a_2 - a_1\\ &\vdots\\ b_l &= a_l - a_{l-1} + c\\ &\vdots\\ b_{r+1} &= a_{r+1} - a_r - c\\ &\vdots\\ \end{align*} $$则数列 $a$ 为：
$$ \begin{align*} a_1 &= b_1\\ a_2 &= b_1 + b_2\\ &\vdots\\ a_l &= b_1 + b_2 + \cdots + b_l + c\\ a_{l+1} &= b_1 + b_2 + \cdots + b_l + c + b_{l+1}\\\ &\vdots\\ a_r &= b_1 + b_2 + \cdots + b_l + c + \cdots + b_r\\ a_{r+1} &= b_1 + b_2 + \cdots + b_l + c + \cdots + b_r + b_{r+1} - c\\ &= b_1 + b_2 + \cdots + b_l + \cdots + b_r + b_{r+1}\\ \end{align*} $$可见区间 $[l,r]$ 内的值都有增加，而这个范围以外保持了原值。实施修改的时间复杂度为 $O(1)$。
参考实现
1vector<int> a(N);
2vector<int> b(N + 1); // avoid out-of-bound write
3
4void updateInterval(int l, int r, int c) {
5 b[l] += c;
6 b[r+1] -= c;
7}
8
9/* Build b[] from a[] */
10for (int i = 0; i < N; ++i) {
11 updateInterval(i, i, a[i]);
12}
13
14/* Retrieve a[] from b[]: Method 1 */
15a[0] = b[0];
16for (int i = 1; i < N; ++i) {
17 a[i] = a[i - 1] + b[i];
18}
19/* Method 2 */
20for (int i = 1; i < N; ++i) {
21 b[i] += b[i - 1];
22}
