从前缀和一步步推导出差分
看一下前缀和数组:
若原数组 a = [3, 1, 2, 5, 7]
则前缀和数组 b = [3,4,6,11,18]
对 a 数组进行操作对应前缀和数组的什么操作?
对 a 数组的某个元素增加c,对应前缀和数组的操作是:
- 对 a[2] 增加 3, 则 b 数组变为:
[3, 4, 6 + 3, 11 + 3, 18 + 3] = [3, 1, 5, 8, 10]
-
原数组 a 的某个元素增加一个数,则对应前缀和数组 s 变化是:该元素及他之后的元素都增加 c
-
也就是: 如果原数组 a[x] 变化,则前缀和数组 s : x 和 x 之后的元素全都变化
根据上面规律,对原数组 a ,如果 a[l] 增加 c, a[r] 减少 c(增加 -c),对应前缀数组 s 的操作是:
- a[l] 增加 c:前缀数组 s的变化是:l 和 l 之后的元素增加 c,如下图:
- a[r] 减少 c:前缀数组 s的变化是:r 和 r之后的元素减少 c,如下图:
- 前缀数组 s 总的变化:s 的[l, r - ]区间的数增加 c,如下图:
总结下就是:
-
原数组的单点操作,对应前缀和数组的区间操作
-
前缀和数组的区间操作,对应原数组的单点操作
来看题目
题目是对 a 数组进行多次区间操作,求变化后 a 数组。
- 如果用暴力的方法做,改变区间元素的时间复杂度:O(n),如果有 m 次操作,总时间负责度是 O(n * m)
如果构造出一个数组 b,b 的前缀和是数组 a,那么对 a 的区间操作,对应b 的单点操作。根据前缀和的性质,可以通过数组 b 求出数组 a,也可以通过数组 a 求出数组 b.
我们在区间操作之前构造出数组 b,那么 a 的区间操作,对应 b 的两点操作。
接下来的若干区间操作,不应用的数组 a 上,而是将该区间操作对应的两点操作应用到b上。等所有操作都完成后,再从 b 还原出数组 a 。
这样,就将区间操作转换成了两点操作。额外付出的代价是:构造数 b,从数组 b 换原出数组 a。m 次区间操作对应的时间复杂度是O(n)。
将 m 次对 a 的区间操作,转换成 m 次对 b 的两点操作,再由 b 换原出 a即可
这里的数组 b 叫做 a 的差分数组。
看一下如何构造出差分数 b:
首先假设a,b都为空数组,也就是全部为0的情况,
因为a[i][j] = b[1][1]+…b[i][j],因为都是0,所有情况满足!
这总情况下,b 数组是 a 数组的差分数组!
实际上,a数组不为空,我们可以把a数组中的值看作(0+a[i][j])。
相当于在数组 a 中, 在区间[i, i] 上加了 a[i].
对应前缀和数组 b的操作是:b[i] += a[i], b[i + 1] -= a[i]
所以:
b[i] = a[i] - a[i - 1]
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int n, m;
int main()
{
cin >> n >> m;
// 读入数组 a
for (int i = 1; i <= n; i ++ ) cin >> a[i];
// 构造差分数组 b
for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];
// 执行m次操作
while(m--)
{
int l, r, k;
// 区间操作转换为两点操作
cin >> l >> r >> k;
b[l] += k;
b[r + 1] -= k;
}
// 通过前缀和,还原数组a
for (int i = 1; i <= n; i ++ )
{
a[i] = a[i - 1] + b[i];
// 输出结果
cout <<a[i]<<" ";
}
return 0;
}
数组b在代码中没有定义