学习笔记：Splay
概念
S p l a y Splay Splay，又叫伸展树，是一种平衡树，通过旋转来实现，可以实现多种一般的平衡树（如 T r e a p Treap Treap）很难或无法在时限内做到的操作。 S p l a y Splay Splay始终保证原序列就是树的中序遍历。
方法
主要是由操作 s p l a y splay splay完成的。 s p l a y splay splay操作可以将点 u u u转到点 k k k的下面。注意该操作要保证 u u u是 k k k的孩子，所以将 a a a挂到 b b b下面需要先把 b b b挂到根再把 a a a挂到 b b b下面。
s p l a y splay splay操作先令父节点为 x x x，二级祖先结点为 y y y。显然 ，当 x = k x=k x=k时结束操作。当 y = k y=k y=k时可以将 u u u旋转上去（不难将旋转的左旋和右旋写到一起）。接下来就要针对于父节点、二级祖先结点（即父节点的父节点）和当前结点的不同状态来分类。因为第一下旋转右旋左旋同理，所以我们假定第一次是右旋，即 x x x是 y y y的左儿子的情况。若 u u u是 x x x的左儿子，则先转 x x x，再转 u u u，否则就转两次 u u u。其实也可以一直转 u u u，但是因为 s p l a y splay splay玄学的时间复杂度证明，就会导致这样做就无法保证时间复杂度是对的，就会 T L E TLE TLE。插入就是二叉查找树的插入方法，但必须要求序列有序才行。为了保证时间复杂度是对的，就要求每次插入后要把当前点转到根（即 s p l a y ( u , 0 ) splay(u,0) splay(u,0)）。
例题
AcWing 2437
首先把所有的数都插入进去。接下来考虑翻转如何实现，不难发现把需要翻转的序列提出来以后，将所有结点的左右子树调换一下即可。直接实现可能会超时，可以用懒标记实现。那如何把需要翻转的序列提出来呢？不难发现把 r + 1 r+1 r+1放到 l − 1 l-1 l−1的下面后， r + 1 r+1 r+1的左子树就是要的序列了。因为 l − 1 l-1 l−1的右子树都比 l − 1 l-1 l−1大，而 r + 1 r+1 r+1比 l − 1 l-1 l−1大，所以转过去后整个 r + 1 r+1 r+1的子树都比 l − 1 l-1 l−1大。又因为 r + 1 r+1 r+1的左子树比 r + 1 r+1 r+1小，所以这就是我们要的序列 l l l到 r r r。然而我们用了 l − 1 l-1 l−1和 r + 1 r+1 r+1，会出边界，所以要在左边和右边加上哨兵，则 l − 1 l-1 l−1变成 l l l， r + 1 r+1 r+1变成 r + 2 r+2 r+2。最后，题目输入的 l l l和 r r r并不是序列的值，而是编号，即第 l l l个点和第 r r r个点，所以要用平衡树里找当前排名是哪个点的函数来找到 S p l a y Splay Splay中对应的点。最后输出中序遍历即可。
#includeAcWing 950
1 1 1和 4 4 4操作都是平衡树的基本操作，不用在意。 2 2 2和 3 3 3操作不难发现一定是群体同加或同减，所以可以用一个值 d e l t a delta delta来暂时存储，注意进来时要减去 d e l t a delta delta，因为他不受目前的工资变化的影响。要求走了几个员工可以用总量减去当前量（平衡树大小）计算。需要注意，每一次 3 3 3操作可能会删除从 a a a开始之前的所有点，所以可以用上一题提出某一个序列的方式，再把左儿子设置成一个不存在的结点就行。找 a a a是平衡树的基本操作，和二叉搜索树查询操作是基本一样的。
#includeAcWing 1063
本题操作都是平衡树最基础的操作，没什么好讲的。但是需要注意的是，我们有可能会把两个平衡树合并。这里就可以用到启发式合并，即把集合内元素较少的插入到元素较大的中。这样可以把时间复杂度控制在可行的范围内。
#includeAcWing 955
第一个操作可以单独对这个序列建一个平衡树再插入到原序列。可以把要插入的点和后一点隔开，即把插入位置后一点挂到要插入的位置编号的下面，然后把新建的树挂到左子树上。第二个操作如AcWing 950。第三个操作可以像线段树一样用一个懒标记。第四个操作同AcWing 2437。第五个操作可以在每一个点存一个当前子树的和 s u m sum sum，然后把序列挑出来（如AcWing 950）即可。最后一个操作要求任意一段的最大子列 m s ms ms可以如AcWing 950把序列挑出来，但是值不好求。我们可以用从最左开始的最大子列 l s ls ls和从最右开始的最大子列 r s rs rs两个值来辅助。每次更新这三个值，令 v v v表示点权， u u u为当前点， l l l为左子树， r r r为右子树则有： u . m s = max ( l . m s , r . m s , l , r s + v u + r . l s ) u.ms=\max(l.ms,r.ms,l,rs+v_u+r.ls) u.ms=max(l.ms,r.ms,l,rs+vu+r.ls) u . l s = m a x ( l . l s , l . s u m + v u + r . l s ) u.ls=max(l.ls,l.sum+v_u+r.ls) u.ls=max(l.ls,l.sum+vu+r.ls) u . r s = m a x ( r . r s , r . s u m + v u + l . r s ) u.rs=max(r.rs,r.sum+v_u+l.rs) u.rs=max(r.rs,r.sum+vu+l.rs)
#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！