可持久化线段树学习笔记

可持久化数据结构初探

操作

请设计一个支持如下操作的数据结构:

  1. 扩大这个数据结构的范围(如从 $[1,n]$ 扩大到 $[1,n + k]$,保证最终的大小不会超过 $10^5$)
  2. 在最新版本基础上修改某个位置上的值
  3. 查询最新版本某个位置上的值
  4. 回滚到某一个版本
  5. 在某一个版本基础上修改某个位置的值
  6. 查询某一个版本某个位置上的值

为了方便,初始时数据结构范围为 $[1,1]$;输入数据均为正整数;每次修改时,都要新建一个版本(基于哪一个版本取决于操作的编号);每次查询时,新建一个与最新版本相同的版本

解析

前置条件:

  1. 数组下标从 1 开始
  2. 一开始就直接开到最大数据结构大小

朴素算法 1

将版本视为一个时间轴,建立一个二维数组,第一维表示版本,第二维存对应版本的数据,每一次操作时把基于的版本复制一遍,然后修改、查询。

时空复杂度 $\mathcal{O}(nm)$,其中 $n$ 为数据结构最大大小,$m$ 为数据结构最大版本数

朴素算法 2

依然将版本视为一个时间轴,建立意义与朴素算法 1 相同的二维数组,不同的是,这次不再复制整个数组,取而代之的是在没有用到的下标 0 处记录这个版本是基于哪个版本的,修改只需修改对应的元素即可。查询时,先看这个元素是不是 0(意味着未被修改),是则跳到下标 0 记录的版本,重复这个过程,直到元素非 0,输出即可

空间复杂度 $\mathcal{O}(nm)$;
修改时间复杂度 $\mathcal{O}(1)$,查询时间复杂度最坏为 $\mathcal{O}(m)$;
$n,m$ 意义同朴素算法 1。

可持久化线段树

为什么要说算法 2 呢?
我个人认为,算法 2 只修改有用的点的特性正符合可持久化线段树的特点。

顺着算法 2 想下去。发现算法 2 有大量无用的空间,怎么办?

搬出树形结构,再加动态开点。

树的结构及修改操作

一棵线段树长这样:

KX0NHU.md.png

然后发现修改第二个元素需要经历这些节点:
KX0gHO.md.png

依据算法 2,开一些新的点作为这个版本的点
KXDUfJ.md.png
蓝点为原来的点,橙点为这个版本经过的点

可以发现它不再是一棵树。但是如果不看那些“被修改”的蓝点,它仍然是一棵二叉树……怎么办?

不妨把它视为多棵线段树,每一棵树都是一个版本,最顶上的依然是树根,只不过这些线段树共享了一些相同的节点

具体实现的话,就把线段树的根节点存在一个数组root[]中,这样,root[i]就表示第 i 棵(第 i 个版本的)线段树的根节点编号。

看一眼代码吧:

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
// 建树,把原始数列建到树的 0 版本上

int roots[]; // 根节点数组

struct Node {
int ls, rs, val;
// ls 表示左儿子编号,rs 表示右儿子编号,val 表示节点信息
} tree[];
int cnt; // 节点编号计数器

void buildTree(int &root, int l, int r) {
// root 要引用的原因是操作过程中
// 要对存放根节点、左儿子(左子树的根节点)、右儿子(右子树的根节点)编号的变量进行更新
// 直接引用变量的话可以省一步赋值,写起来也方便
root = ++cnt; // 给新的节点——当前子树的根节点分配编号
if (l == r) return ((void) (tree[root].val = seq[l]));
// 经典的线段树赋值
int mid = (l + r) >> 1;
buildTree(tree[root].ls, l, mid);
buildTree(tree[root].rs, mid + 1, r);
// 左右子树建树
}

int main() {
// ...
buildTree(roots[0], 1, n);
// 把 0 版本的根节点编号传进去
// ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 修改操作,root 表示当前子树根节点编号,引用也是因为更新方便
// base 表示当前修改的是基于哪个版本的,存的是那个版本「对应深度」子树的根节点编号

void modify(int &root, int base, int l, int r, int pos, int k) {
root = ++cnt; tree[root] = tree[base];
// 分配根节点编号,把节点信息原份复制下来,后面再修改
if (l == r) { tree[root].val = k; return; }
// 经典的单点赋值
int mid = (l + r) >> 1;
if (pos <= mid) modify(tree[root].ls, tree[base].ls, l, mid, pos, k);
else modify(tree[root].rs, tree[base].rs, mid + 1, r, pos, k);
// 对左右子树修改,顺便可以直接更新这个节点的左右儿子信息

int main() {
// ...
modify(roots[新的版本], roots[基于哪个版本], 1, n, 修改的位置, 值);
// ...
}

查询操作

明白了 root[] 数组的意义,查询就很简单了


KX258O.md.png

比如说查询版本 1(初始版本为 0),就是顺着版本 1 的根节点往下找对应位置,查到底部返回。图中灰色的节点是查版本 1 永远碰不到的节点——因为它们在版本 1 中被修改了,而剩下的点依然形成了一棵线段树,顺着这棵树查下去就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 查询操作,root 不加引用是因为查询操作没必要对线段树进行修改
// 经典的单点查询,不讲了

int query(int root, int l, int r, int pos) {
if (l == r) return tree[root].val;
int mid = (l + r) >> 1;
if (pos <= mid) return query(tree[root].ls, l, mid, pos);
else return query(tree[root].rs, mid + 1, r, pos);
}

int main() {
// ...
query(roots[查询的版本], 1, n, 查询的位置);
// ...
}

杂项

扩大数据结构范围

这个其实不用管。。。毕竟一开始就已经把范围开好了

回滚到某个版本

对线段树的具体内容没有一点操作,直接把新版本的根节点编号设为回滚到的版本

1
2
3
4
5
int main() {
// ...
roots[新的版本] = roots[回滚到的版本];
// ...
}

关于数据范围

由于线段树的空间开销本身就很大,再加上可持久化的节点,一般开到原数据范围的 32 倍(即MAXN << 5

代码实现

题目:洛谷P3919《【模板】可持久化数组》
支持的操作:操作 2、3、5、6

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
//
// Created by HandwerSTD on 2019/11/2.
// Copyright (c) 2019 HandwerSTD. All rights reserved.
// Title: 可持久化数组
// Used data structure: 可持久化线段树
//

#include <cstdio>

const int MAXN = 1e6 + 10;

struct Node {
int ls, rs, val;

Node(int _ls = 0, int _rs = 0, int _val = 0) { ls = _ls; rs = _rs; val = _val; }
} tree[MAXN << 5]; int cnt;

int n, m, seq[MAXN], roots[MAXN], versions;

void buildTree(int &root, int l, int r) {
root = ++cnt;
if (l == r) return ((void) (tree[root].val = seq[l]));
int mid = (l + r) >> 1;
buildTree(tree[root].ls, l, mid);
buildTree(tree[root].rs, mid + 1, r);
}

void modify(int &root, int base, int l, int r, int pos, int k) {
root = ++cnt; tree[root] = tree[base];
if (l == r) { tree[root].val = k; return; }
int mid = (l + r) >> 1;
if (pos <= mid) modify(tree[root].ls, tree[base].ls, l, mid, pos, k);
else modify(tree[root].rs, tree[base].rs, mid + 1, r, pos, k);
}

int query(int root, int l, int r, int pos) {
if (l == r) return tree[root].val;
int mid = (l + r) >> 1;
if (pos <= mid) return query(tree[root].ls, l, mid, pos);
else return query(tree[root].rs, mid + 1, r, pos);
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", seq + i);
buildTree(roots[0], 1, n);
for (int i = 1; i <= m; ++i) {
int ver, cmd, loc;
scanf("%d %d %d", &ver, &cmd, &loc);
if (cmd == 1) {
int x; scanf("%d", &x);
modify(roots[++versions], roots[ver], 1, n, loc, x);
} else {
printf("%d\n", query(roots[ver], 1, n, loc));
roots[++versions] = roots[ver];
}
}
return 0;
}