可持久化线段树学习笔记

十一月 03, 2019 5402

可持久化数据结构初探

操作

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

  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;
}