526互联

Splay2

发布时间 2023-04-24 20:45:30作者: untitled0

如果 \(\text{Splay}\) 只能做和 \(\text{RBT、AVL}\) 等一样的功能的话，它除了代码短以外，也就没有什么竞争力了。

它还有一个功能就是可以很方便的维护区间。

和线段树不同， \(\text{Splay}\) 维护区间并没有采用分块的思想，而是利用了自身的性质。

那么进入正题：

\(\text{Splay}\) 维护区间

这里的 \(\text{Splay}\) 维护的不再是点权，而是每个值的在序列中的编号

因此我们需要对二叉搜索树的性质做一些修改：

  1. 空树是二叉搜索树。

  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的编号均小于其根节点的编号。

  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的编号均大于其根节点的编号。

  4. 二叉搜索树的左右子树均为二叉搜索树。

如果我们有一个序列：\(2,6,4,9,1,3,6,4\) ，我们就可以建立一个这样的树：

显然，序列就是这棵树的中序遍历，而且不管如何旋转，中序遍历都是不变的。我们可以利用这个性质对序列进行维护。

这里我们以NOI2003 文本编辑器为例。

在维护区间时，由于不会有多个元素在同一位置，我们的node中的cnt就可以去掉了：

struct node{
    int sz;char val;
    node *fa,*ch[2];
    int get(){return this==fa->ch[1];}
    void upd(){sz=(ch[0]?ch[0]->sz:0)+(ch[1]?ch[1]->sz:0)+1;}
    void rotate(){
        int chk=get();
        node *f=fa,*grd=fa->fa;
        fa->ch[chk]=ch[chk^1];
        if(ch[chk^1])ch[chk^1]->fa=fa;
        ch[chk^1]=f;
        f->fa=this;
        fa=grd;
        if(grd)grd->ch[f==grd->ch[1]]=this;
        f->upd();upd();
    }
};

这些基本操作不熟悉的话可以去OI-wiki。

（此外，本文代码均为指针实现，因为个人觉得指针更直观。）

1. 查找编号为 \(k\) 的元素

显然，和普通平衡树的查第 \(k\) 大是一样的：

node* find(int k){
    node *cur=rt;
    while(cur){
        if(k<=(cur->ch[0]?cur->ch[0]->sz:0))cur=cur->ch[0];
        else {
            k-=(cur->ch[0]?cur->ch[0]->sz:0)+1;
            if(!k)return splay(cur,nullptr),cur;
            //这里splay函数多出来的参数在后面说
            else cur=cur->ch[1];
        }
    }
    return nullptr;
}

2. 选择区间

比如我想把字符串"kkksc03"中的"ksc0"部分选择出来，我们可以将这棵树

中的第二个'k'旋转到根，再将'3'旋转到根的右儿子：

那么显然，红框里面的部分，换句话说，根节点的右儿子的左子树，就是要选择的区间。

因为它是根节点的右儿子的左子树，这个子树中元素的编号就一定在'k'的编号和'3'的编号之间。

那我们如果要选择整个区间呢？哪来的第 \(0\) 个和第 \(n+1\) 个节点呢？

正因如此，我们的树就应该分别在第一个元素前和最后一个元素后面添加一个点，做这第 \(0\) 个和第 \(n+1\) 个节点，保证不出锅。

//为了实现“旋转到根节点”，splay函数多加一个参数goal
void splay(node *cur,node *goal){
    for(node *fa=cur->fa;(fa=cur->fa)!=goal;cur->rotate())
        if(fa->fa!=goal)
            (fa->get()==cur->get()?fa:cur)->rotate();
    if(!goal)rt=cur;
}

void select(int l,int r){
    splay(find(l-1),nullptr);
    splay(find(r+1),rt);
}

3. 删除区间

比如我们要删除"kkksc03"中的"ksc0"，我们只需要在选择区间"ksc0"后把这条边切断即可：

//删除pos后面的len个元素
void del(int pos,int len){
    select(pos+2,pos+len+1);
    rt->ch[1]->ch[0]=nullptr;
    rt->ch[1]->upd();
    rt->upd();
}

至于删掉的那棵子树占用的内存怎么释放，可以另开一个队列或栈存一下以后利用 不过OI不需要考虑这些事

4. 插入区间

如果我们要在"kkksc03"的's'和'c'之间插入字符串"chen_zhe"，我们就先把's'旋转到根节点，'c'旋转到根节点的右儿子，由于它们两个是相邻的，此时根节点的右儿子的左儿子一定为空，我们就在这里插入新的字符串：

接下来处理需要插入的字符串。

我们当然可以把它排成一条链，但这样显然不是最优。因此可以考虑模仿线段树的建树：

//buf是在全局存储需要插入的字符串的数组，是0起的，所以mid要-1
node* build(int l,int r,node *fa){
    if(l>r)return nullptr;
    int mid=(l+r)>>1;
    node *cur=new node;
    cur->fa=fa;
    cur->ch[0]=build(l,mid-1,cur);
    cur->val=buf[mid-1];
    cur->ch[1]=build(mid+1,r,cur);
    cur->upd();
    return cur;
}

那么插入就很简单了：

//在pos后插入len个元素
void insert(int pos,int len){
    select(pos+2,pos+1);
    rt->ch[1]->ch[0]=build(1,len,rt->ch[1]);
}

5. 输出区间

按中序遍历输出：

void print(node *cur){
    if(!cur)return;
    if(cur->ch[0])print(cur->ch[0]);
    if(cur->val!=0&&cur->val!=127)putchar(cur->val);//0和127是虚点
    if(cur->ch[1])print(cur->ch[1]);
}

则 \(\text{Get}\) 操作：

//输出pos后的len个字符
void get(int pos,int len){
    select(pos+2,pos+len+1);
    print(rt->ch[1]->ch[0]);
    putchar(10);
}

6. 结语

那么现在文本编辑器这题就很简单了，只需要维护一个光标位置pos即可。

但是 \(\text{Splay}\) 的功能可不是这么简单，它还可以进行区间反转、区间算术、区间赋值等许多操作，只需要在节点上打上懒标记，在upd()里加几句，再在旋转时加上pushdown即可，正如一位dalao所说： \(\text{Splay}\) 是序列之王。

这里以区间反转（文艺平衡树）为例：

懒标记：

bool rev;

pushdown：

void push_down(){
    if(!rev)return;
    swap(ch[0],ch[1]);
    if(ch[0])ch[0]->rev^=1;
    if(ch[1])ch[1]->rev^=1;
    rev=0;
}

旋转：

void rotate(){
    push_down();fa->push_down();//就多了这两句
    node *f=fa,*grd=fa->fa;
    int chk=get();
    fa->ch[chk]=ch[chk^1];
    if(ch[chk^1])ch[chk^1]->fa=fa;
    ch[chk^1]=f;
    f->fa=this;
    fa=grd;
    if(grd)grd->ch[f==grd->ch[1]]=this;
    f->upd();upd();
}

区间翻转：

void reverse(int l,int r){
    select(l,r);
    if(rt->ch[1]->ch[0])
        rt->ch[1]->ch[0]->rev^=1;
}

\[\mathfrak{End} \]