数列差分

差分是一种对于数列区间修改问题的很优秀的 idea ,对于每个独立的查询操作,它可以做到在线性时间内完成任务……

一 一阶差分

1 模型

维护一段数列,支持将区间 $[l,r]$ 内的每个元素加或减某个值,并查询所有操作后的数列。要求在线性时间内完成任务。

以上为数列差分问题的基本模型。

对于数列$a_1,a_2,a_3,…,a_n$,我们定义它的差分数列为$b_1,b_2,b_3,…b_n$,满足$b_i = a_i-a_{i-1}$。不难发现,有 $a_i=\sum_{j=1}^i b_j$。

我们发现在对区间 $[l,r]$ 进行某次操作之后,该区间内元素的相对大小是不变的,也就是任意两数的差值固定。利用这个性质,我们发现在对一段区间 $[l,r]$ 操作之后,数列 $\begin{Bmatrix} b \end{Bmatrix}$ 中仅有两个元素 $b_l$ 和 $b_{r+1}$ 发生了变化;我们想要记录这次操作的影响,只需要对 $b_l$ 和 $b_{r+1}$ 做一些加加减减就好了。

于是我们做到了在 $O(1)$ 的时间内“传递影响”,那么也就是说我们可以在 $O(q)$ 的时间内处理完所有操作,最后再 $O(n)$ 推一遍前缀和,我们就得到了修改后的 $\begin{Bmatrix} a \end{Bmatrix}$ 数列。

2 代码

代码,实际上差分数组和原序列可以共用一个数组,此处是为了便于理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int CN = 1e6+6;
int n,q,a[CN],b[CN]; // b[] : 差分数组

/* 推 b[] */
a[0] = 0; for(int i=1;i<=n;i++) b[i] = a[i] - a[i-1];

scanf("%d",&q);
while(q--){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
/*
更新 b[] 数组
我们发现 [l,r] + v 会使得 b[r + 1] - v 和 b[l] + v
*/
b[y + 1] -= z; b[x] += z;
}

/* 前缀和推出操作后的 a[] 数组 */
for(int i=1;i<=n;i++) a[i] = a[i-1] + b[i];

更简化的版本:

1
2
3
4
5
6
7
8
9
10
11
12
const int CN = 1e6+6;
int n,q,a[CN];

for(int i=1;i<=n;i++) a[i] = a[i] - a[i-1];

scanf("%d",&q);
while(q--){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
a[y + 1] -= z; a[x] += z;
}

for(int i=1;i<=n;i++) a[i] += a[i-1];


二 二阶差分

1 模型

维护一段数列,支持将区间 $[l,r]$ 加一个等差数列 $s:e$ ( $[l,r]$ 内每个元素分别加等差数列的第 $1,2,3,…$ 项,其中等差数列的第一项为 $s$ ,最后一项为 $e$ ),并查询所有操作后的数列。要求在线性时间内完成任务。

不难发现,某段区间整体加上一个等差数列,相当于该区间上的差分数列整体加了这个等差数列的公差。当然,在差分数列的两个端点还会有一些小的细节。

对于“差分数列整体加公差”这个操作,我们直接对差分数列进差分即可维护。注意,差分数列中加上公差的区间是 $[l+1,r]$ 。

剩下的是一点小细节:区间 $[l,r]$ 加一个等差数列 $s:e$ 后,还会使得 $b_l + s$ 和 $b_{r+1} - e$ 。这两个特例均是对差分数列 $\begin{Bmatrix} b \end{Bmatrix}$ 进行的单点操作,我们在二次差分推出数列 $\begin{Bmatrix} b \end{Bmatrix}$ 后,暴力修改就好了。

2 代码

代码,实际上三个计算数组可以合成一个,此处是为了便于理解:

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
#define LL long long
const int CN = 1e6+6;

LL read(){ /* 省略 */ }

int n,q;
int l[CN],r[CN]; LL s[CN],e[CN]; // 记录操作

LL a[CN],b[CN],c[CN]; // b[] : 原序列的差分
// c[] : 差分序列的差分

/* 推 b[] */
for(int i=1;i<=n;i++) b[i] = a[i] - a[i - 1];
/* 推 c[] */
for(int i=1;i<=n;i++) c[i] = b[i] - b[i - 1];

q = read();
for(int i=1;i<=q;i++){
l[i] = read(); r[i] = read(); s[i] = read(); e[i] = read();
LL k = (e[i] - s[i]) / (r[i] - l[i]); // 公比
/* 更新 c[] 数组 */
c[ r[i] + 1 ] -= k; c[ l[i] + 1 ] += k;
}

/* 推出操作后的 b[] 数组 */
b[0] = 0; for(int i=1;i<=n;i++) b[i] = b[i - 1] + c[i];
/* 对 b[] 进行单点修改 */
for(int i=1;i<=q;i++) b[ r[i] + 1 ] -= e[i], b[ l[i] ] += s[i];

/* 前缀和推出处理后的 a[] 数组 */
a[0] = 0; for(int i=1;i<=n;i++) a[i] = a[i - 1] + b[i];

更简化的版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define LL long long
const int CN = 1e6+6;

LL read(){ /* 省略 */ }

int n,q;
int l[CN],r[CN]; LL s[CN],e[CN],a[CN];

for(int i=1;i<=n;i++) a[i] = a[i] - a[i - 1];
for(int i=1;i<=n;i++) a[i] = a[i] - a[i - 1];

q = read();
for(int i=1;i<=q;i++){
l[i] = read(); r[i] = read(); s[i] = read(); e[i] = read();
LL k = (e[i] - s[i]) / (r[i] - l[i]);
a[ r[i] + 1 ] -= k; a[ l[i] + 1 ] += k;
}

for(int i=1;i<=n;i++) a[i] += a[i - 1];
for(int i=1;i<=q;i++) a[ r[i] + 1 ] -= e[i], a[ l[i] ] += s[i];

for(int i=1;i<=n;i++) a[i] += a[i - 1];

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×