差分是什么

前缀和擅长"快速查一段的和"，差分正好相反，擅长"快速给一段整体加一个数"。想给第 $l$ 到第 $r$ 个数每个都加 $v$，一个个加要改一整段；用差分只要动两个位置：在 $l$ 处 +v，在 $r+1$ 处 -v。

#include <iostream>
using namespace std;
int main() {
    int d[7] = {0};                         // 差分数组，多留一位
    int l = 2, r = 4, v = 5;                // 给第 2~4 个各加 5
    d[l] += v;
    d[r + 1] -= v;                          // 只改两处
    cout << "d[2]=" << d[2] << "  d[5]=" << d[5];  // d[2]=5  d[5]=-5
}

给第 2 到第 4 个各加 5，就是把 d[2] 加 5、d[5] 减 5 这两处。别忘了那个 -v——它负责在区间末尾"关掉"这次加法，漏了它后面的数会被一直多加。