伸展树（Splay tree）学习小结
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
总结一下最近学习的Splay tree。万事开头难啊，像这种神一样的数据结构，刚学是很痛苦的，建议之前要把平衡树，SBT之类的数据结构先学学。
资料都是网上乱翻的，前一两道题，代码主要追随别人，后面慢慢的调整，成为自己的东西。
Splay tree意为伸展树，和别的不同的正是在于它的伸展操作。
在这里，我也证明，解释不了伸展树在时间复杂度，操作上的优势之类的。网上很正规的资料里都会有介绍
伸展树并不是严格意义上的平衡树，也还是极有可能退化成线性结构，但他的伸展操作能使它的每一次操作近似（logn），而且独特的伸展操作能解决一些其它数据结构实现不了的（如线段树，SBT等）。
先说伸展操作，在我的理解中，伸展操作和平衡树的保持平衡是类似的，只不过他不要求保持平衡，只是相应的旋转。
如果旋转的节点的父节点便是目标结点，那么一次旋转即可。但是在平衡树中这一步还要拆开。
举例：现在要将根结点的左孩子右旋操作，而此时如果根的左孩子存在右孩子的话，那么直接旋转过去，新的根便有两个左孩子，显然不可以，所以将左子树先执行左旋，再右旋即可。
如果在伸展树中，父节点并不是目标结点，那就存在爷爷结点，如果爷爷结点和父节点方向一样，那么连续两次上面的右旋或者左旋即可。如果方向不一样，便是一左一右两次旋转。画图比较好理解，大家可以从别的资料中找到图，在伸展树中称为一字型和之字型。虽然说的很复杂，但是在Splay中，代码已经被前辈们优化到很短，很精练。
int Get_interval(int l,int r){Splay(Get_Kth(l-1),0);Splay(Get_Kth(r+1),root);Push_Up(ch[root][1]);Push_Up(root);}这个函数便可以很快找到区间[l,r]执行之后的根的右孩子的左子树便是所要区间，便可以进行操作。 伸展树也可以完成线段树的一些工作，也可以设置延迟标记，向上更新，向下更新等等。具体的在后面的练习中会遇到。
接下来是一些练习。
入门题：可以找一些线段树，或者别的数据结构练练手，操作少，简单。线段树这里有
之后我自己做的一些训练，大多是从这里参考来的
[HNOI2002]营业额统计
第一个Splay,多种数据结构可解。其中主要操作是找到前驱和后继，作为一棵二叉查找树，这并不困难。一个节点的后继，便是右子树中的最左的结点，前驱便是左子树中最右边的节点。
题解这里有
比较经典的线段树题目。将区间先插入到树中，开始便保证有序，之后的操作不改变顺序，注意懒惰标记
题解这里有
之前便排好序，依次保存好下标。依次考虑第K大的，将其旋转至根，左子树的数量便是需要反转的，之后把根删除即可。
题解这里有
题解这里有
HDU 3487 Play with Chain
出现了一个新的操作，CUT。就是旋转，然后删除，然后插入，犀利
题解这里有
保存光标位置，也就是第K大的位置，之后都是Splay经典操作
题解这里有
[NOI2005]维修数列
NOI里非常BT的数据结构题，不过不做过此题，Splay的学习怎么能算完整呢。
其它的都类似，有个最大子列和，不过也类似于线段树里的经典操作
题解这里有