差分是什么

差分是前缀和的“逆运算”：它记录每个数与前一个数的差。设原数列 $a$，差分数列

$$d_1=a_1,d_i=a_i-a_{i-1}(i\ge 2)$$

第一个照抄，后面每个减去前一个。比如 $2,5,10$ 的差分是 $2,3,5$（$2$；$5-2=3$；$10-5=5$）。

d[1] = a[1];
for (int i = 2; i <= n; i++)
    d[i] = a[i] - a[i-1];

奇妙的是它俩互为逆：对差分数列再求一次前缀和，就变回原数列。

$$\sum _{k=1}^i{d}_k=a_i$$

// 差分求前缀和，还原 a
a[0] = 0;
for (int i = 1; i <= n; i++) a[i] = a[i-1] + d[i];

差分本身看着没啥用，真正的威力在下一节：它能把“给一整段区间都加同一个值”变成只改两个位置的事。