526互联

splay（区间）

发布时间 2023-03-30 11:36:00作者: 青阳buleeyes

既然你看到这里，相信你一定了解splay的思想。

splay按照STB的性质进行维护，并将其均摊复杂度降为了log(n)

splay既然被称为序列之王，如此优秀的算法想必还有其他应用。

Splay的区间操作

我们知道查找树的中序遍历是一个有序的序列。这个时候我们不采用查找树左小右大的规则，而是把它的中序遍历作为区间进行维护。

具体来讲有以下操作：

  1. 建树
  2. 区间操作（翻转、赋值...）
  3. 输出序列

建树

对于区间操作，线段树是极佳的选择

void build(int &u,int l,int r,int fa){
    if(l>=r) return ;
    u=++siz;
    int mid=l+r>>1;
    e[u].v=mid;
    e[u].siz=1;
    e[u].f=fa;
    if(l+1<r){
        build(e[u].ch[0],l,mid,u);
        build(e[u].ch[1],mid+1,r,u);
        e[u].siz+=e[e[u].ch[0]].siz+e[e[u].ch[1]].siz;
    }
}

区间操作

这时我们想要从树中查找我们所需的区间，如何操作呢？

splay的伸展操作可以在不改变中序遍历的前提下改变树的结构，也就是说我们可以在不改变序列的前提下改变树的形态。

那么这个时候，如果我们要操作区间 [l,r] 我们只需将 l-1 翻转到根节点，将 r+1 翻转到根节点的右儿子

那么这时，r+1 的左子树就是我们所要的区间 [l,r]

 

如何查找这两个节点？

套用splay的第k大节点好了(这里应该是第k个)

至于找到区间后的操作，采用线段树 lazytag 的思想仍然可以将均摊复杂度降低在 logn

inline void spin(int u){
    int fa=e[u].f,s=isr(u);
    e[u].f=e[fa].f;
    if(e[fa].f) e[e[fa].f].ch[isr(fa)]=u;
    e[fa].ch[s]=e[u].ch[s^1];
    e[fa].f=u;
    if(e[u].ch[s^1]) e[e[u].ch[s^1]].f=fa;
    e[u].ch[s^1]=fa;
    up(fa);
}
void splay(int u,int fa){
    while(e[u].f!=fa){
        if(e[e[u].f].f&&lazy[e[e[u].f].f] pd(e[e[u].f].f);
        if(lazy[e[u].f]) pd(e[u].f);
        if(lazy[u]) pd(u);
        if(e[e[u].f].f==fa) spin(u);
        else if(isr(u)^isr(e[u].f)) spin(u),spin(u);
    }
    if(!fa) root=u;
}

输出序列

对应的中序遍历