「算法笔记」Splay 维护序列

发表于 | | 阅读次数:
字数统计: 849 字
$\text{Splay}$ 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。

例题

我们以「Luogu 3391」文艺平衡树 作为例题：你需要维护一个有序数列，支持翻转区间操作。

分析

总体思路

我们还是用 $\text{Splay}$ 来维护这个序列，但是不用权值维护，而是用节点在序列中的位置为关键字维护，显然一个子树对应一个区间。

每次提取区间 $[l,r]$ 然后将左右子树全部交换。这正是利用了 $\text{Splay}$ 在旋转过程中不会改变中序遍历。那么原来的左根右在交换后变为右根左，实现了区间翻转。

提取区间

根据 $\text{Splay}$ 的特性（具体介绍详见「算法笔记」Splay 维护二叉查找树），对于区间 $[l,r]$，我们可以把 $l-1$ 旋转到根，$r+1$ 旋转到根的儿子（显然是右儿子）。那么根的右儿子的左子树就是区间 $[l,r]$。

对于这里的 $l-1$ 和 $r+1$，指的是序列中第 $l-1$ 和第 $r+1$ 个元素对应的节点，而不是下标为 $l-1$ 和 $r+1$ 的节点。因此我们要调用 $\text{Splay}​$ 基本操作中的 kth(l-1) 和 kth(r+1) 找到对应的节点编号。

交换子树

我们这里要使用一个和线段树很相似的懒标记，我们对于每个节点记录一个 $\text{rev}​$ 标记，标记这个区间是否被翻转。每次 kth 操作时将标记下传、交换左右子树、清空自身标记。

时间复杂度：$O(n\log n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <cstdio>
#include <algorithm>

const int N=1e5+5;
const int INF=1<<30;
int n,m,rt,idx,ch[N][2],fa[N],sz[N],cnt[N],val[N],rev[N];

void pushup(int x) {
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
void pushdown(int x) {
    if(rev[x]) {
        std::swap(ch[x][0],ch[x][1]);
        rev[ch[x][0]]^=1;
        rev[ch[x][1]]^=1;
        rev[x]=0;
    }
}
bool get(int x) {
    return ch[fa[x]][1]==x;
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    ch[z][get(y)]=x,fa[x]=z;
    ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y;
    ch[x][k^1]=y,fa[y]=x;
    pushup(y),pushup(x);
}
void splay(int x,int g) {
    while(fa[x]!=g) {
        int y=fa[x];
        if(fa[y]!=g) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
    if(!g) rt=x;
}
int kth(int x) {
    ++x;
    int u=rt;
    while(1) {
        pushdown(u);
        if(x>sz[ch[u][0]]+cnt[u]) x-=sz[ch[u][0]]+cnt[u],u=ch[u][1];
        else if(x<=sz[ch[u][0]]) u=ch[u][0];
        else return u;
    }
}
void ins(int x) {
    int u=rt,f=0;
    while(x!=val[u]&&u) f=u,u=ch[u][x>val[u]];
    if(u) ++cnt[u];
    else {
        u=++idx;
        if(f) ch[f][x>val[f]]=u;
        ch[u][0]=ch[u][1]=0,fa[u]=f,val[u]=x,sz[u]=cnt[u]=1;
    }
    splay(u,0);
}
int main() {
    scanf("%d%d",&n,&m);
    ins(-INF),ins(INF);
    for(int i=1;i<=n;++i) ins(i);
    while(m--) {
        int l,r;
        scanf("%d%d",&l,&r);
        splay(kth(l-1),0),splay(kth(r+1),rt);
        rev[ch[ch[rt][1]][0]]^=1;
    }
    for(int i=1;i<=n;++i) {
        printf("%d%c",val[kth(i)]," \n"[i==n]);
    }
    return 0;
}

习题

详见「算法笔记」Splay 维护二叉查找树。

0%