跳转至

可持久化平衡树

Split-Merge Treap


对于无旋 Treap 的提示

看楼上的 Treap 词条

OI 常用的可持久化平衡树 一般就是 可持久化无旋转 Treap 所以推荐首先学习楼上的 无旋转 Treap

思想 / 做法

我们来看看旋转的 Treap,为什么不能可持久化呢?

如果带旋转,那么就会破环原有的父子关系,破环原有的路径和树形态,这是可持久化无法接受的。

如果把 Treap 变为非旋转的,我们发现可以通过可持久化 MergeSplit 操作就可以完成可持久化.

「一切可支持操作都可以通过 Merge Split Newnode Build 完成」,而 Build 操作只用于建造无需理会,Newnode(新建节点) 就是用来可持久化的工具。

我们来观察一下 MergeSplit ,我们会发现它们都是由上而下的操作!

因此我们完全可以参考线段树的可持久化操作对它进行可持久化。

可持久化操作

可持久化是对数据结构的一种操作,即保留历史信息,使得在后面可以调用之前的历史版本.

对于可持久化线段树来说,每一次新建历史版本就是把沿途的修改路径复制出来

那么对可持久化 Treap (目前国内 OI 常用的版本) 来说:

在复制一个节点 X_{a} ( X 节点的第 a 个版本) 的新版本 X_{a+1} ( X 节点的第 a+1 个版本) 以后:

  • 如果某个儿子节点 Y 不用修改信息,那么就把 X_{a+1} 的指针直接指向 Y_{a} ( Y 节点的第 a 个版本) 即可。
  • 反之,如果要修改 Y ,那么就在递归到下层新建 Y_{a+1} ( Y 节点的第 a+1 个版本) 这个新节点用于存储新的信息,同时把 X_{a+1} 的指针指向 Y_{a+1} ( Y 节点的第 a+1 个版本)。

可持久化

需要的东西:

  • 一个 struct 数组 存每个节点的信息 (一般叫做 tree 数组); (当然写指针版平衡树的大佬就可以考虑不用这个数组了)

  • 一个根节点数组,存每个版本的_树根_,每次查询版本信息时就从根数组存的节点开始;

  • split() 分裂 从树中分裂出两棵树

  • merge() 合并 把两棵树按照随机权值合并

  • newNode() 新建一个节点

  • build() 建树

Split

对于分裂操作,每次分裂路径时新建节点指向分出来的路径,用 std::pair 存新分裂出来的两棵树的根。

std::pair <int,int> split(x,k) 返回一个 std::pair;

表示把 _x 为根的树的前 k 个元素放在一棵树中,剩下的节点构成在另一棵树中,返回这两棵树的根(first 是第一棵树的根,second 是第二棵树的)。

  • 如果 x 左子树 key ≥ k ,那么直接递归进左子树,把左子树分出来的第二颗树和当前的 x 右子树合并。
  • 否则递归右子树
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
static std::pair<int, int> _split(int _x, int k) {
  if (_x == 0)
    return std::make_pair(0, 0);
  else {
    int _vs = ++_cnt;  //新建节点(可持久化的精髓)
    _trp[_vs] = _trp[_x];
    std::pair<int, int> _y;
    if (_trp[_vs].key <= k) {
      _y = _split(_trp[_vs].leaf[1], k);
      _trp[_vs].leaf[1] = _y.first;
      _y.first = _vs;
    } else {
      _y = _split(_trp[_vs].leaf[0], k);
      _trp[_vs].leaf[0] = _y.second;
      _y.second = _vs;
    }
    _trp[_vs]._update();
    return _y;
  }
}

Merge

int merge(x,y) 返回 merge 出的树的根。

同样递归实现。如果 x 的随机权值 > y 的随机权值 ,则 merge(x_{rc},y) ,否则 merge(x,y_{lc})

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
static int _merge(int _x, int _y) {
  if (_x == 0 || _y == 0)
    return _x ^ _y;
  else {
    if (_trp[_x].fix < _trp[_y].fix) {
      _trp[_x].leaf[1] = _merge(_trp[_x].leaf[1], _y);
      _trp[_x]._update();
      return _x;
    } else {
      _trp[_y].leaf[0] = _merge(_x, _trp[_y].leaf[0]);
      _trp[_y]._update();
      return _y;
    }
  }
}

Luogu P3835 可持久化平衡树

题目背景

本题为题目 普通平衡树 的可持久化加强版。

数据已经经过强化

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):

  1. 插入 x 数

  2. 删除 x 数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)

  3. 查询 x 数的排名(排名定义为比当前数小的数的个数 + 1。若有多个相同的数,因输出最小的排名)

  4. 查询排名为 x 的数

  5. 求 x 的前驱(前驱定义为小于 x,且最大的数,如不存在输出 -2147483647)

  6. 求 x 的后继(后继定义为大于 x,且最小的数,如不存在输出 2147483647)

和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本(操作 3, 4, 5, 6 即保持原版本无变化)。

每个版本的编号即为操作的序号(版本 0 即为初始状态,空树)

输入格式:

第一行为 n,表示操作的个数, 下面 n 行每行有两个数 opt 和 x,opt 表示操作的序号 (1 \leq x \leq le6)

输出格式:

对于操作 3,4,5,6 每行输出一个数,表示对应答案。

题解简述

就是普通平衡树一题的可持久化版,操作和该题类似..

只是使用了可持久化的 merge 和 split 操作

推荐的练手题

  1. luogu P3919 可持久化数组 (模板题)

  2. codeforces 702F T-shirt

另外

  1. 可持久化平衡树可以用来维护动态凸包,仙人掌等东西,如果读者有兴趣可以阅读相应的 计算几何 知识,再来食用。

  2. Zip Tree 作为一种新的数据结构在 2018.8 月由 Robert E. Tarjan - Caleb C. Levy - Stephen Timmel 提出,可以去了解一下~


评论