QAQ

WBLT学习笔记

发表于 更新于

Description

一种基于leafy tree维护的加权平衡树。

Leafy Tree

通过判断一棵树的数据存储位置在每个节点上还是仅在叶子节点上，我们可以将树分为 Nodey 和 Leafy 的。Leafy Tree被定义为一种维护的信息全部储存在叶子节点上的二叉树。这种结构中，每个叶子存贮值，每个非叶节点值负责维护树的形态而不维护树的信息，但通常会维护孩子信息的并来加速查询。线段树的结构属于一种Leafy Tree。

注意到，一个Leafy结构的每个节点必定有两个孩子。对其进行插入删除时，在插入删除叶子时必定会额外修改一个非叶节点。

常见的平衡树均属于每个节点同时维护值和结构的Nodey Tree。如果将一个Nodey结构的所有孩子的空指针指向一个维护值的节点，那么这棵树将变为一个Leafy结构。

Leafy Tree是一个纯函数化的数据结构，因此其在实现函数化数据结构和可持久化效率上具有先天优势，而且时间效率极高。

BST实现

考虑用Leafy Tree构造一棵BST来实现维护动态集合的操作。不难看出，维护类似BST的性质只需保证叶子节点有序即可。令每个非叶子节点都仅记录其右儿子的权值（子树中最大值），并满足中序遍历中所有叶节点的值有序。每次操作直接从根节点开始遍历，到某个节点时比较其和子树的最大值的相对关系递归遍历。

插入时遍历到叶子节点之后将其转化为虚点，同时新建两个节点储存原本的信息和插入的值。删除时直接找到删除节点的兄弟节点，之后用其覆盖掉父亲即可。

Leafy Tree在实现时的优势在于其只有叶子节点存储了真正的信息，因而省去了其他平衡树繁杂的分类讨论过程。

加权平衡树

加权平衡树上的每个节点依靠设定一个权重作为平衡限制来进行平衡度维护，即Balanced
by Boundary。这类平衡限制通常是子树大小，不难看出替罪羊树即为一种加权平衡树。更一般地，对于一棵二叉树，如果其每个节点 $x$ 都满足：

则称该节点是 $\alpha$ 加权平衡的。此时称 $\alpha$ 为平衡因子。‘

Leafy Tree可以使用不同的平衡方式维护，但实践中一般用加权平衡方式。在这种局部的平衡方式下Leafy Tree具有clj定义的重量平衡树性质，即每次维护平衡影响到的最大子树大小是 $O(\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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1,c=getchar();
    while(c<48) c=='-'&&(f=-1),c=getchar();
    while(c>47) x=x*10+c-'0',c=getchar();
    return x*f;
}

const int MAXN = 200005;
int size[MAXN],val[MAXN],ch[MAXN][2];
int n,tot,root;

inline void pushup(int x)
{
    if(!ch[x][0]) return;
    size[x]=size[ch[x][0]]+size[ch[x][1]];
    val[x]=val[ch[x][1]];
}

inline int newnode(int k)
{return size[++tot]=1,val[tot]=k,tot;}

inline void rotate(int x,int k)
{
    int w=ch[x][k],p=ch[x][k]=ch[x][k^1];
    ch[x][k^1]=ch[p][k^1]; ch[p][k^1]=ch[p][k];
    ch[p][k]=w; pushup(ch[x][0]); pushup(ch[x][1]);
}

inline void maintain(int x)
{
    if(!ch[x][0]) return;
    if(size[ch[x][0]]>=size[ch[x][1]]) rotate(x,1);
    if(size[ch[x][1]]>=size[ch[x][0]]) rotate(x,0);
}

inline void insert(int x,int k)
{
    if(!ch[x][0])
    {
        ch[x][0]=newnode(min(val[x],k));
        ch[x][1]=newnode(max(val[x],k));
        return pushup(x),void();
    }
    insert(ch[x][k>val[ch[x][0]]],k);
    pushup(x); maintain(x);
}

inline void erase(int x,int f,int k)
{
    if(!ch[x][0])
    {
        if(val[x]^k) return;
        int w=ch[f][ch[f][0]==x]; val[f]=val[w];
        ch[f][0]=ch[w][0]; ch[f][1]=ch[w][1];
        return size[f]=size[w],void();
    }
    erase(ch[x][k>val[ch[x][0]]],x,k);
    pushup(x); maintain(x);
}

inline int rnk(int x,int k)
{
    if(!ch[x][0]) return (k>val[x])+1;
    if(k<=val[ch[x][0]]) return rnk(ch[x][0],k);
    return size[ch[x][0]]+rnk(ch[x][1],k);
}

inline int kth(int x,int k)
{
    if(!ch[x][0]) return val[x];
    if(k<=size[ch[x][0]]) return kth(ch[x][0],k);
    return kth(ch[x][1],k-size[ch[x][0]]);
}

int main(int argc, char const *argv[])
{
    n=read(); root=newnode(1e9);
    for(int i=1,opt,x; i<=n; ++i)
    {
        opt=read(); x=read();
        if(opt==1) insert(root,x);
        if(opt==2) erase(root,0,x);
        if(opt==3) printf("%d\n",rnk(root,x));
        if(opt==4) printf("%d\n",kth(root,x));
        if(opt==5) printf("%d\n",kth(root,rnk(root,x)-1));
        if(opt==6) printf("%d\n",kth(root,rnk(root,x+1)));
    }
    return 0;
}

串接与拆分

串接和拆分操作的定义为合并或拆分为两个值域不交的平衡树上的信息。对于两个Nodey结构的树，merge操作相当于需要将两个点集通过各种方法串接起来，而Leafy的结构仅需要新建一个中间节点，再将原本的两棵树作为其左右儿子，其外点的信息就会自然合并在一起。这种写法的复杂度并不正确，但实践中是速度最快的。

对于拆分（split）操作，常用实现是将根节点到拆分位置的所有非叶节点递归删除，再另外在向上回溯时递归合并两侧的节点。注意到这些操作均是可以利用Path-Copy进行可持久化的。

Leafy Tree一般仅用这种操作维护序列，因为可以通过加权平衡的方式更为方便的维护权值信息。可以依靠分裂合并高效地支持区间操作。

例题：【模板】文艺平衡树

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0,f=1,c=getchar();
    while(c<48) c=='-'&&(f=-1),c=getchar();
    while(c>47) x=x*10+c-'0',c=getchar();
    return x*f;
}

const int MAXN = 200005;
int s[MAXN],st[MAXN],ch[MAXN][2];
int rev[MAXN],size[MAXN];
int n,m,tot,top,root;

inline void pushup(int x)
{size[x]=size[ch[x][0]]+size[ch[x][1]];}

inline void pushr(int x)
{swap(ch[x][0],ch[x][1]),rev[x]^=1;}

inline void pushdown(int x)
{
    if(!ch[x][0]) return;
    if(rev[x])
    {
        if(ch[x][0]) pushr(ch[x][0]);
        if(ch[x][1]) pushr(ch[x][1]);
        rev[x]=0;
    }
}

inline int newnode(int k)
{
    int x=top?st[top--]:++tot; s[x]=k,size[x]=1;
    return ch[x][0]=ch[x][1]=rev[x]=0,x;
}

inline int join(int x,int y,int p=newnode(0))
{return ch[p][0]=x,ch[p][1]=y,pushup(p),p;}

inline int merge(int x,int y)
{
    if(!x||!y) return x|y;
    return join(x,y);
}

void split(int p,int k,int &x,int &y)
{
    if(!k) return x=0,y=p,void();
    if(!ch[p][0]) return x=p,y=0,void();
    int &ls=ch[p][0],&rs=ch[p][1];
    if((pushdown(p),1)&&k>size[ls])
        split(rs,k-size[ls],x,y),x=merge(ls,x);
    else split(ls,k,x,y),y=merge(y,rs);
    st[++top]=p;
}

inline void rever(int l,int r)
{
    int x,y,z; split(root,l-1,x,y);
    split(y,r-l+1,y,z); pushr(y);
    root=merge(merge(x,y),z);
}

inline int build(int l,int r)
{
    if(l==r) return newnode(l);
    int mid=(l+r)>>1;
    return join(build(l,mid),build(mid+1,r));
}

void dfs(int x)
{
    pushdown(x);
    if(ch[x][0]) dfs(ch[x][0]);
    if(!ch[x][0]) printf("%d ", s[x]);
    if(ch[x][1]) dfs(ch[x][1]);
}

int main(int argc, char const *argv[])
{
    n=read(); m=read(); root=build(1,n);
    for(int i=1,l; i<=m; ++i)
        l=read(),rever(l,read());
    return dfs(root),0;
}