Ryan_<

Learned from %%%DeadFishYSY

extract from cxlove（泥不是爱酱，喵~~）

如果旋转的节点的父节点便是目标结点，那么一次旋转即可。但是在平衡树中这一步还要拆开。

如果父节点并不是目标结点，那就存在爷爷结点，如果爷爷结点和父节点方向一样，那么连续两次上面的右旋或者左旋即可。如果方向不一样，便是一左一右两次旋转。在伸展树中称为一字型和之字型。

虽然说的很复杂，但是在Splay中，代码已经被前辈们优化到很短，很精练。

void Rotate(int x,int kind){   //kind分别代表左右旋 
    int y=pre[x];      
    Push_Down(y);  
    Push_Down(x);  
    ch[y][!kind]=ch[x][kind];     
    pre[ch[x][kind]]=y;    
    if(pre[y])    
        ch[pre[y]][ch[pre[y]][1]==y]=x;    
    pre[x]=pre[y];    
    ch[x][kind]=y;    
    pre[y]=x;    
    Push_Up(y);    
}     
//将节点r旋转至goal
void Splay(int r,int goal){    
    Push_Down(r);  
    while(pre[r]!=goal){    
        if(pre[pre[r]]==goal)    
            Rotate(r,ch[pre[r]][0]==r);    
        else{    
            int y=pre[r];    
            int kind=(ch[pre[y]][0]==y);    
            if(ch[y][kind]==r){    
                Rotate(r,!kind);    
                Rotate(r,kind);    
            }    
            else{    
                Rotate(y,kind);    
                Rotate(r,kind);    
            }    
        }    
    }    
    Push_Up(r);    
    if(goal==0) root=r;    
}

这样的伸展操作对于我们的区间操作有什么优势呢。

可以想一个问题，对于一个区间[l,r]，对于平衡树，SBT，如果很快定位到这个区间是很困难的，面对于线段树是可以做到的，那么如果要把区间进行删除，旋转，线段树便做不到了。

接下来看看Splay tree是怎么做的，首先伸展树本质还是个二叉查找树。做法也很简单，将第l-1个结点旋转至根（之前的Splay操作），将第r+1个结点旋转至根的右孩子，那么根据二叉查找树我们知道，在这两个结点之间，也是根的右孩子的左子树就包括节点[l,r]，我们便很快定位，如果需要删除，直接便可以把子树拿走。其中Get_Kth表示找到第K个结点，记录子树的大小，便可以很快实现。

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]执行之后的根的右孩子的左子树便是所要区间，便可以进行操作。 

伸展树也可以完成线段树的一些工作，也可以设置延迟标记，向上更新，向下更新等等。具体的在后面的练习中会遇到。。。。。吧（@zyf）