可持久化线段树

主席树

主席树全称是可持久化权值线段树,参见 知乎讨论

关于函数式线段树

函数式线段树 是指使用函数式编程思想的线段树。在函数式编程思想中,将计算机运算视为数学函数,并避免可改变的状态或变量。不难发现,函数式线段树是 完全可持久化

引入

先引入一道题目:给定 个整数构成的序列 ,将对于指定的闭区间 查询其区间内的第 小值。

你该如何解决?

一种可行的方案是:使用主席树。 主席树的主要思想就是:保存每次插入操作时的历史版本,以便查询区间第 小。

怎么保存呢?简单暴力一点,每次开一棵线段树呗。
那空间还不爆掉?

解释

我们分析一下,发现每次修改操作修改的点的个数是一样的。
(例如下图,修改了 中对应权值为 1 的结点,红色的点即为更改的点)

只更改了 个结点,形成一条链,也就是说每次更改的结点数 = 树的高度。
注意主席树不能使用堆式存储法,就是说不能用 来表示左右儿子,而是应该动态开点,并保存每个节点的左右儿子编号。
所以我们只要在记录左右儿子的基础上,保存插入每个数的时候的根节点就可以实现持久化了。

我们把问题简化一下:每次求 区间内的 小值。
怎么做呢?只需要找到插入 r 时的根节点版本,然后用普通权值线段树(有的叫键值线段树/值域线段树)做就行了。

这个相信大家都能理解,回到原问题——求 区间 小值。
这里我们再联系另外一个知识:前缀和
这个小东西巧妙运用了区间减法的性质,通过预处理从而达到 回答每个询问。

我们可以发现,主席树统计的信息也满足这个性质。
所以……如果需要得到 的统计信息,只需要用 的信息减去 的信息就行了。

至此,该问题解决!

关于空间问题,我们分析一下:由于我们是动态开点的,所以一棵线段树只会出现 个结点。
然后,有 次修改,每次至多增加 个结点。因此,最坏情况下 次修改后的结点总数会达到 。 此题的 ,单次修改至多增加 个结点,故 次修改后的结点总数为 ,忽略掉 ,大概就是

最后给一个忠告:千万不要吝啬空间(大多数题目中空间限制都较为宽松,因此一般不用担心空间超限的问题)!大胆一点,直接上个 ,接近原空间的两倍(即 n << 5)。

实现

 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
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5;  // 数据范围
int tot, n, m;
int sum[(maxn << 5) + 10], rt[maxn + 10], ls[(maxn << 5) + 10],
    rs[(maxn << 5) + 10];
int a[maxn + 10], ind[maxn + 10], len;

inline int getid(const int &val) {  // 离散化
  return lower_bound(ind + 1, ind + len + 1, val) - ind;
}

int build(int l, int r) {  // 建树
  int root = ++tot;
  if (l == r) return root;
  int mid = l + r >> 1;
  ls[root] = build(l, mid);
  rs[root] = build(mid + 1, r);
  return root;  // 返回该子树的根节点
}

int update(int k, int l, int r, int root) {  // 插入操作
  int dir = ++tot;
  ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1;
  if (l == r) return dir;
  int mid = l + r >> 1;
  if (k <= mid)
    ls[dir] = update(k, l, mid, ls[dir]);
  else
    rs[dir] = update(k, mid + 1, r, rs[dir]);
  return dir;
}

int query(int u, int v, int l, int r, int k) {  // 查询操作
  int mid = l + r >> 1,
      x = sum[ls[v]] - sum[ls[u]];  // 通过区间减法得到左儿子中所存储的数值个数
  if (l == r) return l;
  if (k <= x)  // 若 k 小于等于 x ,则说明第 k 小的数字存储在在左儿子中
    return query(ls[u], ls[v], l, mid, k);
  else  // 否则说明在右儿子中
    return query(rs[u], rs[v], mid + 1, r, k - x);
}

inline void init() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  memcpy(ind, a, sizeof ind);
  sort(ind + 1, ind + n + 1);
  len = unique(ind + 1, ind + n + 1) - ind - 1;
  rt[0] = build(1, len);
  for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

int l, r, k;

inline void work() {
  while (m--) {
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]);  // 回答询问
  }
}

int main() {
  init();
  work();
  return 0;
}

拓展:基于主席树的可持久化并查集

主席树是实现可持久化并查集的便捷方式,在此也提供一个基于主席树的可持久化并查集实现示例。

 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
74
75
76
77
78
79
80
81
82
83
#include <algorithm>
#include <cstdio>
const int N = 1e5, M = 2e5;  // 数据范围

struct node {
  int val, rank, lchild, rchild;
} tree[4 * N + M * 19];  // 每次操作增加节点数最多为 log2(4 * N) = 19

int init[N + 1], root[M + 1], tot;

int build(int l, int r) {  // 建树
  int now = ++tot;
  if (l == r) {
    tree[now].val = init[l];
    tree[now].rank = 1;
    return now;
  }
  int mid = l + r >> 1;
  tree[now].lchild = build(l, mid);
  tree[now].rchild = build(mid + 1, r);
  return now;
}

int update(int x, int l, int r, int target,
           int newroot) {  // 合并操作-更新父亲节点信息
  int now = ++tot;
  tree[now] = tree[x];
  if (l == r) {
    tree[now].val = newroot;
    tree[newroot].rank = std::max(tree[newroot].rank, tree[now].rank + 1);
    return now;
  }
  int mid = l + r >> 1;
  if (target <= mid)
    tree[now].lchild = update(tree[x].lchild, l, mid, target, newroot);
  else
    tree[now].rchild = update(tree[x].rchild, mid + 1, r, target, newroot);
  return now;
}

int query(int x, int l, int r, int target) {  // 查询父亲节点
  if (l == r) return tree[x].val;
  int mid = l + r >> 1;
  if (target <= mid)
    return query(tree[x].lchild, l, mid, target);
  else
    return query(tree[x].rchild, mid + 1, r, target);
}

int getroot(int x, int l, int r, int target) {  // 查询根节点
  int ans = query(x, l, r, target);
  if (ans == target)
    return ans;
  else
    return getroot(x, l, r, ans);
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) init[i] = i;
  root[0] = build(1, n);
  int op, a, b, k;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &a, &b);
      int root_a = getroot(root[i - 1], 1, n, a);
      int root_b = getroot(root[i - 1], 1, n, b);
      if (tree[root_a].rank < tree[root_b].rank)  // 按秩合并
        root[i] = update(root[i - 1], 1, n, root_a, root_b);
      else
        root[i] = update(root[i - 1], 1, n, root_b, root_a);
    } else if (op == 2) {
      scanf("%d", &k);
      root[i] = root[k];
    } else {
      scanf("%d%d", &a, &b);
      root[i] = root[i - 1];
      printf("%d\n", getroot(root[i], 1, n, a) == getroot(root[i], 1, n, b));
    }
  }
}

参考

https://en.wikipedia.org/wiki/Persistent_data_structure

https://www.cnblogs.com/zinthos/p/3899565.html


评论