【算法】差分
差分
- 1.【模板】差分
- 2.海底高铁
- 3.【模板】二维差分
- 4.地毯
差分的核心思想是预处理，可以在暴力枚举的过程中，快速解决在某一段区间的所有元素统一加上一个数的操作，获取最终结果，从而优化时间复杂度。是经典的用空间替换时间的做法。前缀和与差分是一对互逆的运算。
1.【模板】差分
【模板】差分
解法：差分
差分模板题，先「创建」差分数组，然后根据差分数组的「性质」处理 q 次区间修改，最后「还原」出来原始的数组。
- 创建差分数组，根据定义：f[i] = a[i] − a[i − 1]。也可以根据差分数组的性质：f[i] += a[i], f[i + 1] −= a[i]。
- 根据差分数组的性质对区间 [L, R] 内的数据加 c 操作：f[L] += c, f[R + 1] −= c。
- 还原经过 q 次询问之后的 a 数组：对差分数组做一次「前缀和」，就可以还原出原数组。
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL a[N];
LL f[N]; //差分数组
int main()
{
cin >> n >> m;
//预处理差分数组
for(int i = 1; i <= n; i++)
{
cin >> a[i];
f[i] = a[i] - a[i - 1];
}
//处理 m 次修改操作
while(m--)
{
int l, r, k; cin >> l >> r >> k;
f[l] += k;
f[r + 1] -= k;
}
//还原原数组：差分数组求前缀和
for(int i = 1; i <= n; i++)
{
a[i] = a[i - 1] + f[i];
cout << a[i] << " ";
}
return 0;
}
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL f[N]; //差分数组
int main()
{
cin >> n >> m;
//利用差分数组的性质，预处理差分数组
for(int i = 1; i <= n; i++)
{
LL x; cin >> x;
f[i] += x;
f[i + 1] -= x;
}
//处理 m 次修改操作
while(m--)
{
LL l, r, k; cin >> l >> r >> k;
f[l] += k;
f[r + 1] -= k;
}
//还原原数组：差分数组求前缀和
for(int i = 1; i <= n; i++)
{
f[i] = f[i - 1] + f[i];
cout << f[i] << " ";
}
return 0;
}
2.海底高铁
P3406 海底高铁
解法：差分
先考虑如何让花费最小，想要求最小花费，需要知道每一段高铁被「乘坐了多少次」，记作 f[i]，那么最小花费就是「买票的花费」与「买卡的花费」两者之间的最小值：
- 买票花费：a[i] × f[i]。
- 买卡花费，乘车花费 + ⼯本费：b[i] × f[i] + c[i]。
- 那么最小花费就是：mincost = min(a[i] × f[i], b[i] × f[i] + c[i])。
接下来考虑如何求出每一段⾼铁被「乘坐了多少次」。根据访问城市的序列 p1, p2, p3, …, pm 可知，对于任意一次访问 pi ~ pj，我们会乘坐 [pi, pj - 1] 之间所有的高铁，比如 pi = 3，pj = 6，那么 [3, 5] 之间所有的高铁都会被乘坐一次，相当于每个数都加上 1，「注意 6 位置不会乘坐到」。那么我们就可以利用「差分数组」：
- 创建一个全为 0 的差分数组 f。
- 遍历访问序列，对于每一次访问：f[pi]++, f[pj]−−。
- 然后对差分数组做一次前缀和，就得到每个高铁乘坐的次数。
注意城市访问的序列有可能 pi > pj，此时应该「交换」一下顺序。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL f[N]; //差分数组
int main()
{
cin >> n >> m;
int x; cin >> x;
//预处理差分数组
for(int i = 2; i <= m; i++)
{
int y; cin >> y;
// x->y
if(x > y)
{
f[y]++;
f[x]--;
}
else
{
f[x]++;
f[y]--;
}
x = y;
}
//还原原数组：差分数组求前缀和（各个路线乘坐的次数）
for(int i = 1; i < n; i++)
{
f[i] = f[i - 1] + f[i];
}
LL ret = 0;
for(int i = 1; i < n; i++)
{
LL a, b, c; cin >> a >> b >> c;
ret += min(a * f[i], b * f[i] + c);
}
cout << ret;
return 0;
}
3.【模板】二维差分
【模板】二维差分
解法：差分
二维差分模板题，先根据差分矩阵的「性质」创建差分矩阵，然后根据差分矩阵的「性质」处理 q 次
区间修改，最后利用「前缀和」还原出来原始的矩阵。因此，重点就是差分矩阵的「性质」。可以类比「一维差分数组」的性质，推导出「⼆维差分矩阵」的性质：
- 在差分数组中某个位置标记：表示后续元素统一被修改。
- 在差分数组中求前缀和：能够还原出原始数组。
假设我们需要将原始矩阵 a 中，以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵的每个元素都加
上 k：
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int n, m, q;
LL f[N][N]; //差分数组
//模版：差分矩阵的性质
void insert(int x1, int y1, int x2, int y2, LL k)
{
f[x1][y1] += k;
f[x1][y2 + 1] -= k;
f[x2 + 1][y1] -= k;
f[x2 + 1][y2 + 1] += k;
}
int main()
{
cin >> n >> m >> q;
//预处理差分矩阵
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
LL x; cin >> x;
//[i, j]为左上角，[i, j]为右下角的矩阵，统一加上x
insert(i, j, i, j, x);
}
}
//处理 q 次修改操作
while(q--)
{
LL x1, y1, x2, y2, k; cin >> x1 >> y1 >> x2 >> y2 >> k;
insert(x1, y1, x2, y2, k);
}
//还原出原数组：差分数组求前缀和
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
cout << f[i][j] << " ";
}
cout << endl;
}
return 0;
}
4.地毯
P3397 地毯
解法：差分
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int f[N][N]; //差分矩阵
//差分矩阵的性质
void insert(int x1, int y1, int x2, int y2)
{
f[x1][y1]++;
f[x1][y2 + 1]--;
f[x2 + 1][y1]--;
f[x2 + 1][y2+ 1]++;
}
int main()
{
cin >> n >> m;
//构建差分矩阵
while(m--)
{
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
insert(x1, y1, x2, y2);
}
//利用前缀和还原为修改之后的矩阵
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
cout << f[i][j] << " ";
}
cout << endl;
}
return 0;
}