Nukxx @ 2019-01-01 19:22:17
蒟蒻想问一下 每一个节点的编号都代表什么呀······假如每一个数有权值 比如 1 7 6 2 3，要求设计算法能维护翻转操作，每一个节点的编号又代表什么啊······QAQ急求助 愿大佬帮忙！！！感激不尽
by Nukxx @ 2019-01-01 19:49:25
不要沉啊QAQ
by 重力做功 @ 2019-01-31 14:16:05
理解一下splay在序列上的表示。
splay是平衡树对吧。
平衡树是什么？是一种二分查找树对吧。
二分查找树是什么？"左儿子的值<结点的值<右儿子的值"对吧。
对吧。
对吧。
不对了233。
在序列上，二分查找树的定义被改成了这样：
左儿子在序列上都在当前结点的左侧，右儿子在序列上都在当前结点的右侧。
没有理解没有关系，上例子。
有一个序列。
{A,B,C,D,E}。
有一个splay，对应着这个序列。
（当然可以捣鼓出一大堆splay都可以对应着个序列。）
下面这个splay就是合法的：
(B)
/ \
(A) (D)
/ \
(C) (E)现在应该理解这个二分查找树的定义了吧（这很重要）。
为什么要搞出这样的定义？意义何在？
{A,B,C,D,E}。
(B)
/ \
(A) (D)
/ \
(C) (E)我要知道第4个元素，就是要访问D。
我在splay上怎么找到它呢？
我先从根开始对吧。
那我在B号结点，不知所措。
往左走还是往右走呢？
诶啊，左边只有1个东东。
也就是说，我发现B号结点应该在左边那1个东东的右侧，也就是说B号结点居然在第2位！
可是我要找第4位。
那么第4位就应该在B号结点的右边。
所以我去找B号结点的右儿子中的第2位。递归下去。
然后你会发现刚才这个操作居然就是在平衡树中查找"第pos小"的过程。
有了刚才的解释，应该就不难理解别人博客上说的所谓"l-1 r+1"分别旋一旋的操作了吧。
所以我也懒得打字。
by 斯茂 @ 2019-02-21 19:14:39
%%%巨佬tql！