Splay 伸展树

by 蒟蒻XZY 2017.12.28

-1. 注

以下用数组模拟链表,不用指针。

未说明的情况下定义的节点结构体为:



其中$f$为父节点编号,$s[0]$为左儿子,$s[1]$为右儿子,$d$为该节点的值,$sz$为该节点大小。

$SIZE$为节点个数。

$0$号节点为空节点($NULL$)

还有一些定义:



一. 操作

0. 申请节点&垃圾回收

搞个栈就行了,复杂度$O(1)$



1. Build操作

因为我们需要一颗平衡的树,所以我们每次找中间位置为子树的根,再递归建立左右子树(区间)。

复杂度$O(n)$



2. Pos操作

获取点a为左儿子(0)还是右儿子(1),很方便,因为在我的模板中节点的左右儿子分别为$s[0],s[1]$,可以直接用这个操作获取下标。

复杂度$O(1)$



3. Push_up操作

一般来说就是类似递归地通过儿子更新父亲,如更新节点a的sz

复杂度$O(1)$



4. Push_down操作

一般比较繁杂

但是谨记一个要点:

时刻保证你需要访问的节点是最新的!

就是更新某个节点的话,先手动改了这个节点的值,再给这个节点打上标记。

别只打标记,再在push_down中看是否有标记在更新这个节点,不然可能会错。



对于上面那个代码,比如我们要整棵树的值都加上k,则:



也就是先改值,再打标记

复杂度$O(1)$

5. Rotate操作

本来分为左旋、右旋,现在将其简化为:把节点a提到其父节点上方

复杂度$O(1)$

见代码:



6. Splay操作

整个Splay的核心,用来调整树的高度。

代码用for循环实现,很短,复杂度$O(log_2n)$



注:上面代码若要旋到根则:$splay(a,0)$

7. Insert操作

插入一个节点的操作,同二叉查找树。

只是插入完后记得splay那个新的节点。

复杂度$O(log_2n)$



8. 找第k大值操作

也和二叉查找树一样。

复杂度$O(log_2n)$



9. 提取区间操作

原理:二叉查找树的性质:左子树值<父节点值<右子树值。

设我们要提取区间$[l,r]$

那我们就先将节点$l-1$ Splay到根,然后再把节点$r+1$ Splay到$l-1$下面,这样以$r+1$ 的左儿子为根的子树就是我们所要提取的区间了。所有区间$[l,r]$中的元素都包含在该子树内。

因为可能出现提取整个区间的端点($1$或$n$),但$1-1$或者$n+1$都越界了,所以我们需要在整个区间两端添加两个“哨兵节点”

我习惯于设左边的哨兵节点编号为$1$,右边的为$n+2$,所以中间的原序列对应的节点编号都$+1$了。

那么提取原序列区间$[l,r]$的操作应该这么写:



显然复杂度为$O(log_2n)$

10. 插入区间

设我们要在第$pos$个元素后面插入$len$个元素($pos$为$0$则插入在首部)

​先把需要插入的元素放到$data$数组中,然后提取区间$[pos+1,pos+1]$ ,再把那$len$个元素$build$成一棵树,最后把这棵树接到刚刚提取出来的区间(空的区间)上,然后记得push_up root的右儿子和root(要依次push_up)。

复杂度$O(n)$



11. 删除区间

递归删除,复杂度$O(n)$



12. 翻转区间

先提取区间,然后更换区间对应的子树根的左右儿子,再给这个子树根打上标记。

复杂度$O(log_2n)$



13. 输出区间

递归实现,复杂度$O(n)$



二. 习题&代码

0. 文艺平衡树

LOJ - 105,BZOJ - 3223

题解:传送门= ̄ω ̄=

代码:

1. 序列终结者

BZOJ - 1251

题解:传送门= ̄ω ̄=

代码:

2. 维修数列

BZOJ - 1500

题解:传送门= ̄ω ̄=

令人窒息の题目

代码:

3. 郁闷的出纳员

BZOJ - 1503

题解:传送门= ̄ω ̄=

好模板!就是有点坑,一开始工资就低于标准的人直接不算进入过公司。因为这个WA了好久啊!(>_<)

代码:

4. Editor

BZOJ - 1507

题解:传送门= ̄ω ̄=

同 0.维修数列,还简单些。

代码:


还有很多,不做过多赘述。

推荐习题列表

//注:题解不一定是splay的!n(≧▽≦)n

还有更多操作等待你的发现!