背景
今天在 leetcode 上偶然刷到一题：1094. 拼车，让我想起了之前用到的差分数组法求区间问题。之前由于种种原因忘记了总结，现在我要好好总结一下，就怕日后不常使用又把它忘了。
举例
我们假设有两个数组 a 和 b ：
a : 1, 2, 4, 5, 6
b : 1, 1, 2, 1, 1
假如我们要求数组 b 中某一段连续子数组的元素之和，比如 b[1]+b[2]+b[3]，其实我们就可以用 a[3] - a[0] 来表示，总之，b[i...j] = a[j] - b[i-1]。
这是因为数组 a 是数组 b 的前缀和数组，即 a[i] = b[0] + b[1] + ... + b[i]。这样我们就可以通过数组 b 的前缀和数组 a 来快速求得数组 b 的某一段连续子数组之和，只需要知道该区间的前后位置即可。
反之，如果我们想对数组 a 的某一段连续子数组进行相同的加减操作，比如对 a[1..3] 进行加10操作，那么我们可以通过遍历一遍 a[1], a[2], a[3]，使其加上10，得到新数组: 1, 12, 14, 15, 6。
但是该方法复杂度太高，其实我们可以利用数组 b，只需要对数组 b 的 b[1] 进行加 10 操作，对 b[4] 进行减 10 操作即可，这样得到的新的数组 b 为：1, 11, 2, 1, -9。然后再对该数组求前缀和即可得到新数组 a。
咋一看时间复杂度也不低，但是这就是其时间复杂度的上限，即使需要操作的区间很多，也不会影响其复杂度。也就是该方法能保证线性的时间复杂度。
数组 b 就是数组 a 的差分数组。
总结
前缀和数组和差分数组是一对互相关系，数组 a 是数组 b 的前缀和数组，那么数组 b 就是数组 a 的差分数组。
前缀和数组可以用来处理某一段区间的连续元素和，差分数组可以用来处理某一段区间的相同的加减操作。
两者关系很简单，几句话就能说明白，但是如果不进行总结，遇到题目还是很难想出来，所以我就另外找了一个题目用于练手，就是 acwing 里的 797. 差分。
题目描述
输入一个长度为n的整数序列。
接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数序列。
接下来m行，每行包含三个整数l，r，c，表示一个操作。
输出格式
共一行，包含n个整数，表示最终序列。
数据范围
$1 \le n,m \le 100000,$
$1 \le l \le r \le n,$
$-1000 \le c \le 1000,$
$-1000 \le 整数序列中元素的值 \le 1000$
输入样例：
6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1输出样例：
3 4 5 3 4 2
普通解法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> n >> m;
vector<int> arr(n);
for (int i = 0; i < n; ++i) cin >> arr[i];
int l, r, c;
for (int i = 0; i < m; ++i) {
cin >> l >> r >> c; //获取区间以及c
for (int j = l; j <= r; ++j) { //遍历区间,对区间内的元素全部加上c
arr[j-1] += c;
}
}
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
差分解法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> n >> m;
vector<int> arr(n+1), b(arr);
for (int i = 1; i <= n; ++i) cin >> arr[i]; //构造原始数组
for (int i = 1; i <= n; ++i) b[i] = arr[i] - arr[i-1]; //构造差分数组
int l, r, c;
for (int i = 0; i < m; ++i) {
cin >> l >> r >> c;
//更改差分数组区间两头元素，从而使得原始数组该区间中元素全部加上c
b[l] += c;
b[r+1] -= c;
}
for (int i = 1; i <= n; ++i) {
//由差分数组构造出新的原始数组并输出
b[i] = b[i-1] + b[i];
cout << b[i] << " ";
}
return 0;
}