差分与前缀和
绪论
差分与前缀是两个相反的过程,其中差分旨在以递推的形式记录数组元素,前缀和是以求和的方式灵活地面对区间询问
区间加常数
给定一个序列𝑎(初值全为0)。有很多次操作，每个操作形如： l r k
意为将
𝑎[𝑙,𝑟]中的每个值加上𝑘最后输出整个数组。 复杂度要求O(𝑛).允许离线
这个有朴素的算法,就是老老实实一点点加,但是面对大量数据,就显得力不从心(复杂度O(n^2)).
所以我们从差分的角度思考这个问题.不妨设数组左边界为L,右边界是R,且有L<=l<=r<=R,
那么在区间加前后,除了a[l]与a[r+1]元素与前一位元素的差值改变了之外,剩下的均无变化,这样也就保证了能在O(1)的时间内完成一个区间加的操作,我们不妨用数组p[]来记录差值,也就是p[i]表示a[i]-a[i-1]
综上所述
1
2
3
4
5
6
7
8
9
10
11
12
// 数组均初始化为0
int a[MAXN]; // 原数组,本质上是差分数组的前缀和
int p[MAXN]; // 差分数组
void add(int l,int r,int k){ // 区间加,复杂度O(1)
p[l]+=k;
p[r+1]-=k;
}
void get_a(){ // 生成a数组,复杂度O(n)
for(int i=1;i<=n;++i){ // 自1开始记数且保证a[0]为0
a[i]=a[i-1]+p[i];
}
}
区间加等差数列
给定一个序列𝑎(初值全为0)。有很多次操作，操作有两种， 强制在线：
- 区间加等差数列 指定[𝑙,𝑟]，指定等差数列𝑓的首项和公差。 𝑎[𝑙,𝑟]每一个元素加上对应的元素： 𝑎[𝑙] += 𝑓1,𝑎[𝑙+1] += 𝑓2,⋯
- 单点查询 指定𝑥，求𝑎𝑥. e.g. 目前a={1,2,3,3,3,3}，给[3,5]加上首项为2、公差为1的等差数列。 A变为： {1,2,5,6,7,3}
我们还是考虑其差分数组,对于p来说,其在(l,r]区间内的元素均加了一个常数d(公差),p[l]改为f1(首项),p[r+1]也改变了,需要减去此等差数列的最后一项
我们根据前文区间加的经验可以得知,我们只需要再创建一个数组作为p的差分数组,就可以在O(1)时间内解决这个问题,我们将这个数组命名为r[]
然后我就发现我想多了,p[]目前需要满足单点修改和区间加和区间询问,需要用线段树才能解决
区间乱七八糟求和
给定序列𝑎，有𝑛次询问。每次询问指定[𝑙,𝑟]. 要你回答: \(ans=\sum_{i=l}^{r}(r-i+1)a_i\) e.g. 查询[3,5]，则有： ans =
3*a[3]+2*a[4]+1*a[5]
ans = 5𝑎4 + 4𝑎5 + 3𝑎6 + 2𝑎7 + 𝑎8 = 5𝑎4 + 4𝑎5 + 3𝑎6 + 2𝑎7 + 𝑎8 + 5𝑠3 − 5𝑠3= 𝑠4 + 𝑠5 + 𝑠6 + 𝑠7 + 𝑠8 − 5𝑠3
也就是此求和问题可以根据s[]求得,但是频繁的询问下计算量也很大,所以我们再对s求前缀和,就能在O(1)时间内回答每个询问了.
例题
简述题意:
你有一个长为n的栅栏,标号[1…n],你有q个粉刷匠,每个人有一个l,r,即在[l,r]范围内的栅栏都可以粉刷,现在你只能雇佣q-2个人,求最长的粉刷范围
题意很简单,做法也很暴力,就是穷举所有可能,但是如何让计算粉刷范围变得简单呢?
换句话说,我们穷举出两个不雇佣的,怎样快速求得其他人的粉刷面积呢?
此题思路非常巧妙
我们先让所有人粉刷,然后扫描数组,记录每个点被多少条线段覆盖过,顺便计算出有多少点被覆盖了,记作sum,然后用one和two两个数组来记录只被一条/两条线段覆盖过的点的数量的前缀和,
然后穷举所有组合,求出A-B(并集减交集)中所有仅被一条线段覆盖的点的数量,以及和A∩B中所有仅被两条线段覆盖的的点的数量,然后和sum作差就得到了去除AB两条线段后剩余点的数量,继续枚举,最后输出最值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// http://codeforces.com/contest/1132/problem/C
// 非常nice的一道题,考察了前缀和的思想
// 差分和前缀和例题
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
using namespace std;
int l[5010]; // 记录线段所有左端点
int r[5010]; // 记录线段所有右端点
int a[5010]; // a[i]表示i号节点有几个线段可以覆盖它
int one[5010]; // one[i]记录[1,n]中有几个点仅被一条线段覆盖
int two[5010]; // two[i]记录{1,n]中有几个点仅被两条线段覆盖
int main() {
int q, n;
cin >> n >> q;
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
// 值得一提的是此处,当时没掌握差分思想,只能暴力模拟,实际上下面的for里面可以写成 ++p[l],--p[r+1];
// 然后在处理one,two数组的时候仿照之前的例子把a[]给递推出来
for (int j = l[i]; j <= r[i]; ++j) {
++a[j];
}
}
// 记录能被线段覆盖的点的个数
int sum = 0;
// 预处理上述所有数组
for (int i = 1; i <= n; ++i) {
one[i] = one[i - 1] + (a[i] == 1);
two[i] = two[i - 1] + (a[i] == 2);
sum += (a[i] != 0);
}
int maxn = 0;
// 暴力穷举所有选择可能,
// 不妨设两个线段交集为[l,r]然后去除在此范围内的仅被两条线段能覆盖的点的数量
// 不妨设两个线段并集减交集的区间为[l',r'],然后去除在此范围内的,仅被一条线段覆盖的点的数量
for (int i = 0; i < q - 1; ++i) {
for (int j = i + 1; j < q; ++j) {
int l1 = l[i];
int l2 = l[j];
int r1 = r[i];
int r2 = r[j];
int ans = 0;
if (l1 > l2) {
swap(l1, l2);
swap(r1, r2);
}
int tmp = min(l2, r1);
// 左半并集
ans += one[tmp] - one[l1 - 1];
tmp = min(r1, r2);
// 交集(可能为空)
ans += max(0, two[tmp] - two[l2 - 1]);
if (r1 < r2) {
swap(l1, l2);
swap(r1, r2);
}
tmp = max(l1, r2);
// 右半并集
ans += one[r1] - one[tmp - 1];
maxn = max(maxn, sum - ans);
}
}
cout << maxn << endl;
return 0;
}
