RainAir
My OI Blog
RainAir
Splay 学习笔记 · 续

之前我写的 平衡树学习笔记 大体介绍了一下两种平衡树。这里详细的介绍 Splay 。
主要是从代码层面详细介绍,默认读者已经掌握了基本原理。

Splay 代码详解

结构体定义

$ch$ 指针指向这个节点的左右儿子,$val$ 表示该节点表示的元素的值,$cnt$ 表示该元素出现了几次,$size$ 表示以该节点为子数的值

一些结构体函数

Rotate 操作

这里我们使用异或来把左旋和右旋合并成一个代码,如果对该过程有疑问清参考我之前的平衡树文章。

Splay 操作

这里注意的是每个指针都要引用和判断一下空指针。

Split 操作和 Merge 操作

Split 操作就是首先将 $val$ 节点旋转到根然后分为左子树和右子树。
Merge 直接合并,比线段树合并简单 $qwq$。

Insert 操作和 Erase 操作

Insert 操作原理:如果已经存在就将这个元素旋转到根并且更新 $cnt$,否则按照 Split 出来的两棵子树中间合并上一个新节点。
Erase 操作原理:将元素旋转到根。如果删除一次后仍存在则更新cnt,否则将其左右子树合并并且删除该节点(可选)。

其他查询操作

Pre 操作:等价于将序列取反后进行 upper_bound。这里只需要将 $val $ 伸展到根并且判断一下根节点是不是 $val$ 就可以了。
Succ 操作:等价于 upper_bound。和 Pre 操作同理,就是判断有一些小细节不一样。
GetRank 操作:查询一个数的排名,将 $val$ 旋转到根,这个数的排名就是小于它的数的数量 $+1$,即该节点左子树的 $size$ 加上 $1$。
GetKth 操作:查询排名为 $k$ 的数,用另一种伸展方式将排名为 $k$ 的数伸展到根即可。

终于写完了 $qaq$ 其实 Splay 也不是那么的难….并且还能适用于一些其他的数据结构例如 LCT
那我们来看另一道用 Splay 维护区间信息的题目吧 $qwq$.

「BZOJ3223」文艺平衡树

题目链接

题目描述

您需要写一种数据结构(可不参考题目标题),来维护一个有序数列,其中需要提供以下操作:
– 翻转一个区间,
例如原有序序列是5 4 3 2 1,翻转区间是 $[2,4]$ 的话,结果是5 2 3 4 1
设序列长度为 $n$,有 $n \leq 10^5$。

题解

其实区间操作也不是那么难 $qwq$
首先我们维护这些数的位置。如果把它们扔进 Splay 之后我们发现查询第 $i$ 个数实际上就是查询 Splay 里排名第 $i$ 的数。
区间翻转相当于交换了左右子树。
所以维护一个翻转标记然后每次访问节点前交换左右子树并且下方标记就好啦 $qwq

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/143
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

Splay 学习笔记 · 续
之前我写的 平衡树学习笔记 大体介绍了一下两种平衡树。这里详细的介绍 Splay 。 主要是从代码层面详细介绍,默认读者已经掌握了基本原理。 Splay 代码详解 结构体定义 [crayon-5dcee…
扫描二维码继续阅读
2018-10-28
标签
近期评论