Splay学习笔记

Splay是个很神奇的数据结构。

这是一道模板题。

这道题可以用$Splay$，$FHQ\ treap$，$\dots$来解决。

Splay的基本操作

首先我们考虑正常的二叉查找树，添加的部分只是在查询到某个节点的时候一直将该节点向上左旋/右旋到根。

这样看起来并没有什么作用，但是一些神仙们就据此发明了$Splay\ Tree$。

$Splay$并不需要像其他的平衡树那样对于每一个节点多维护一个平衡因子（就是保证树平衡的东西辣），而是通过神奇的旋转使得其均摊复杂度为$O(log\ n)$。

旋转有两种情况，分别被叫做$Zig-Zig​$和$Zig-Zag​$：

$A、B、C、D$都是子树，$x、y、z$是节点。

然后每次访问到$x$这个节点的时候就从底下一路将其转到上面即可。

最重要的就是左旋、右旋的$rotate$函数和将$x$转到现在$t$所在位置的$splay$函数。

$rotate$函数十分厉害，把左旋和右旋放到了一起：

1
2
3
4
5
6
7
8
9
10

void rotate(int x, int &t) {
    int y = node[x].fa, z = node[y].fa;
    int tp = node[y].ch[1] == x;
    if (y == t) t = x;
    else node[z].ch[node[z].ch[1] == y] = x;
    node[x].fa = z; node[y].fa = x;
    node[y].ch[tp] = node[x].ch[tp ^ 1];
    node[node[y].ch[tp]].fa = y;
    node[x].ch[tp ^ 1] = y;
}

这个函数的作用是将$x$旋转到原本是其父亲所在的位置。

先找到$x$的父亲$y$，$x$的祖父$z$，判断$x$是$y$的左儿子还是右儿子（$tp$），并且将$z$原来是$y$的儿子改为$x$

然后改一下$x$和$y$的父子关系，以及把$x$原来的左/右子树（是和$tp$不一样的那个）给$y$。

$splay$函数就是单纯的向上旋转，但是也很巧妙地将原本要判断的4种情况改为了直接判断$x、y、z$是否在一条直线上，非常厉害：

1
2
3
4
5
6
7

void splay(int x, int &t) {
    while (x != t) {
        int y = node[x].fa, z = node[y].fa;
        if (y != t) rotate((node[z].ch[1] == y) ^ (node[y].ch[1] == x) ? x : y, t);
        rotate(x, t);
    }
}

然后插入、删除都和正常的二叉查找树无异，只是别忘了将要访问的节点先$splay$到根再说。

Splay的高级操作

和$FHQ\ treap$一样，$Splay$也支持区间操作。

不同的是，$FHQ\ treap$是将要修改的区间所对应的子树硬生生$split$出来，而$Splay$通过将要改的区间$[l,r]$中$l-1$旋转到根，再把$r+1$旋转到$l-1$的右儿子，就会发现$r+1$的左子树就是要更改的区间。其中的道理也是很简单的，就是利用了二叉查找树的性质：$[l,r]$中的每个数都大于$l-1$，小于$r+1$。然后就可以在那个子树中打上要修改的标记了。也用$pushdown$操作来将标记下推。

要注意的是，如果儿子的值会影响父亲的，要在$rotate$的最后加上上浮语句，将$x、y、z$都更改（它们的儿子都发生了变化）。

代码