数据结构Part 3

每一种平衡树会分 P 讲。

0.定义

平衡树，说白了它还是个 BST，只不过朴素 BST 的所有操作复杂度是 $\Omicron(h)$ 的，可以构造数据卡成 $\Omicron(n ^ 2)$ 。

这个时候，就可以用各种神奇方法来维护这个 BST 的平衡，使其树高为 $\Omicron(\log n)$ 。

Treap 这种平衡树用的是~~数学期望~~堆的性质，一个点，除了自己的值外，我们再维护一个随机权值，然后让值满足 BST 的性质，权值满足堆的性质。

一般平衡树维护平衡的方式是通过旋转（替罪羊树除外，那玩意是暴力美学），而 FHQ Treap 就不用，它用分裂 + 合并。

但是，能不写平衡树的题尽量不要写平衡树，因为常数会大的飞起来。

权值树状数组跑 260ms 的，平衡树能跑 672ms。

1.实现

我们维护以下信息：

1
struct Node
2
{
3
    int ls,rs, // 左右儿子
4
    val, // 值
5
    rank, // 随机权值
6
    size; // 子树大小
7
}tree[MAXN];
8
int root,cnt; // 根结点，结点个数（指针式不需要）
9
#define lson(rt) tree[rt].ls
10
#define rson(rt) tree[rt].rs

新建结点

我觉得没什么好讲的。

1
random_device seed;
2
mt19937 rnd(seed());
3
// 上面是随机数生成器
4
inline int newNode(int val) // 新建结点，并返回其编号
5
{
6
    ++cnt;
7
    lson(cnt) = rson(cnt) = 0,
8
    tree[cnt].val = val,
9
    tree[cnt].rank = rnd(),
10
    tree[cnt].size = 1; // 自己大小为 1
11
    return cnt;
12
}

统计子树大小

也没什么好讲的，就是注意一下自己这个结点也算进该子树。

1
inline void pushup(int rt)
2
{
3
    tree[rt].size = tree[lson(rt)].size + tree[rson(rt)].size + 1;
4
}

合并

我们传入两个值：L,R，表示待合并的左右子树的根结点，返回一个值：合并完成后的根结点。

因为这两个树都是已经平衡的 FHQ Treap，所以我们只用考虑谁在上，谁在下。

如果某一个结点为 $0$ ，说明已经合并完成了，直接返回另一个结点。

否则，我们比较两个点的随机权值（不用特别区分大小，因为随机权值没有利用价值），然后递归向下合并。

若左子树在上，就合并根结点的右儿子和右根结点，否则合并右根结点的左儿子和左根结点。

合并完成后，更新子树大小。

只要看懂了就很好写出代码。

1
inline int merge(int L,int R)
2
{
3
    if(!L || !R)
4
        return L | R;
5
    if(tree[L].rank < tree[R].rank)
6
    {
7
        rson(L) = merge(rson(L),R);
8
        pushup(L);
9
        return L;
10
    }
11
    else
12
    {
13
        lson(R) = merge(L,lson(R));
14
        pushup(R);
15
        return R;
16
    }
17
}

分裂

这个分两种：按值分裂和按排名分裂（序列平衡树里面用）

按值分裂

将一棵 FHQ Treap 按值分裂，小于等于这个值的分到左边，大于的分到右边

回顾一下 FHQ Treap 的形态，值满足 BST，权值满足堆。

也就是说，一个结点的左儿子的值小于自己的值，右儿子的值大于自己的值。

因此，我们对于每一个结点，与目标值比较，如果小于，更新左树的根为此结点，前往右子树接着分裂；反之，就前往左子树。

代码如下：

1
inline void splitVal(int rt,int val,int &L,int &R) // 注意，要更新，所以是引用
2
{
3
    if(!rt)
4
    {
5
        L = R = 0;
6
        return ;
7
    }
8
    if(tree[rt].val <= val)
9
    {
10
        L = rt;
11
        splitVal(rson(rt),val,rson(rt),R);
12
    }
13
    else
14
    {
15
        R = rt;
16
        splitVal(lson(rt),val,L,lson(rt));
17
    }
18
    pushup(rt); //记得更新这个结点的信息
19
}

按排名分裂

还是类似，不过这次比较的是目标排名和左子树的大小加一。

如果左子树的大小小于排名，则应该前往右子树，同时排名也需要更新（可以理解为已经考虑了自己和左子树）。反之，就前往左子树。

代码如下：

1
inline void splitRank(int rt,int rk,int &L,int &R)
2
{
3
    if(!rt)
4
    {
5
        L = R = 0;
6
        return ;
7
    }
8
    if(tree[lson(rt)].size < rk)
9
    {
10
        L = rt;
11
        splitRank(rson(rt),rk - tree[lson(rt)].size - 1,rson(rt),R);
12
    }
13
    else
14
    {
15
        R = rt;
16
        splitRank(lson(rt),rk,L,lson(rt));
17
    }
18
    pushup(rt);
19
}

最重要的两个操作就讲完了。

接下来我们分普通平衡树（值域树）和文艺平衡树（序列树）

普通平衡树

插入

由于 merge 只是合并起来，不能自动排序，所以我们需要在 $val - 1$ 处按值分裂，然后新建一个结点，与分裂出的两棵树合并。

代码如下：

1
inline void insert(int val)
2
{
3
    int x,y;
4
    splitVal(root,val - 1,x,y);
5
    root = merge(merge(x,newNode(val)),y);
6
}

删除

我们可以按照值，把树分裂为三段： $[-\infty,val - 1],val,[val + 1,\infty]$ ，然后把 $[-\infty,val - 1]$ 和 $[val + 1,\infty]$ 合并。

如果只删一个，就合并中间那段的根结点的左右儿子，然后处理掉根结点。

代码如下：

1
inline void remove(int val)
2
{
3
    int x,y,z;
4
    splitVal(root,val - 1,x,y);
5
    splitVal(y,val,y,z);
6
    pool[++top] = y; // 扔进垃圾桶
7
    y = merge(lson(y),rson(y))
8
    root = merge(merge(x,y),z);
9
}

求 K 小值

类似按排名分裂，如果左子树大小加一与 $K$ 相等，则直接输出该结点的值；如果大于，则前往左儿子，否则前往右儿子。

可以写迭代，会快一点：

1
inline int queryKth(int k)
2
{
3
    int rt = root;
4
    while(rt)
5
    {
6
        if(tree[lson(rt)].size + 1 == k)
7
            break;
8
        else if(tree[lson(rt)].size >= k)
9
            rt = lson(rt);
10
        else
11
        {
12
            k -= tree[lson(rt)].size + 1;
13
            rt = rson(rt);
14
        }
15
    }
16
    return tree[rt].val;
17
}

求排名

可以直接分裂，左树大小加一就是排名：

1
inline int queryRank(int val)
2
{
3
    int x,y;
4
    splitVal(root,val - 1,x,y);
5
    int res = tree[x].size + 1;
6
    root = merge(x,y);
7
    return res;
8
}

求前驱

我们按照值分出两棵树，然后找到左树的右链底，就是该值的前驱。

解释一下，由于 BST 的性质，一个结点的右儿子一定大于该结点的值，所以右链链底一定是该树中最大的值。

为什么不用查排名配合 K 小值呢？因为这样常数会小点。

1
inline int queryPrev(int val)
2
{
3
    int x,y,rt;
4
    splitVal(root,val - 1,x,y);
5
    rt = x;
6
    while(rson(rt))
7
        rt = rson(rt);
8
    root = merge(x,y);
9
    return tree[rt].val;
10
}

如何判断无解？没有左树就无解。

求后继

类似，分裂以后右树左链链底就是答案。

1
inline int queryNext(int val)
2
{
3
    int x,y,rt;
4
    splitVal(root,val,x,y);
5
    rt = y;
6
    while(lson(rt))
7
        rt = lson(rt);
8
    root = merge(x,y);
9
    return tree[rt].val;
10
}

快速建树

我们把每一个值直接插入树的建树方法有的时候还是太慢了。这个时候我们就可以用笛卡尔树的建树法。先排序，然后从中点处分开，对左右区间分别建树后合并就好了。

这个是通用的，只不过权值树需要排序。

1
inline int build(int l,int r)
2
{
3
    if(l == r)
4
        return newNode(a[l]);
5
    int mid = (l + r) >> 1,rt = newNode(a[mid]);
6
    lson(rt) = build(l,mid - 1),rson(rt) = build(mid + 1,r);
7
    pushup(rt);
8
    return rt;
9
}

文艺平衡树

前面说了，FHQ Treap 的值满足 BST 的性质，于是我们可以将下标看作值，值额外记录。这样我们就可以让 FHQ Treap 支持区间操作。

这里是需要用按排名分裂的。

当我们想操作区间 $[l,r]$ 时，我们可以将整个 FHQ Treap 分裂成三段： $[1,l - 1],[l,r],[r + 1,n]$ ，然后对中间那段进行操作，操作完了直接合并回去就好了。

但是，中间那个区间可能奇长无比，可以卡到你 T 飞，所以，我们可以运用线段树的懒标记思想。

其实就是每次操作以后，在这个结点处打个标记，然后分裂和合并这种需要访问子结点的操作，就把标记下放。

类似下面：

1
inline void pushdown(int rt)
2
{
3
    if(tree[rt].haveTag)
4
    {
5
        if(lson(rt)) //防止给空结点赋一些奇奇怪怪的值
6
            update(lson(rt));
7
        if(rson(rt))
8
            update(rson(rt));
9
        tree[rt].clearTag();
10
    }
11
}

其实这种懒标记思想是通用的，值域树也可以打懒标记。

但是要注意的是，FHQ Treap 是 Nody Tree，一定要注意这个结点也需要更新。

所以，~~你可以把 Seg Beats 那一堆全部搬过来让你的代码长度更上一层楼~~。

2.常用优化技巧

因为平衡树的时空常数都大的离谱，所以卡常就很重要。

空间优化

对于删除的结点，我们可以重复利用空间。

就是在删除结点的时候，我们记录该结点的编号，压到一个栈里。在 newNode 的时候，优先使用栈里面的结点，栈空了才申请额外空间。

时间优化

最常用的就是上面的快速建树法。

由于 FHQ Treap 和 Splay 的常数都大的飞起，所以只用值域树的题可以用 STL/PBDS 封装好的红黑树，区间树可以换成 WBLT。

3.可持久化

由于 FHQ Treap 的分裂与合并都不会调整祖先关系，所以可以很方便的可持久化。

分裂的时候，把涉及到的结点全部复制一遍，合并的时候也是，也就比不可持久化的多了两行。

1
inline int copyNode(int o)
2
{
3
    ++cnt;
4
    lson(cnt) = lson(o),rson(cnt) = rson(o);
5
    tree[cnt].rank = rnd();
6
    tree[cnt].val = tree[o].val;
7
    tree[cnt].size = tree[o].size;
8
    return cnt;
9
}
10
inline int merge(int L,int R)
11
{
12
    if(!L || !R)
13
        return L | R;
14
    if(tree[L].rank < tree[R].rank)
15
    {
16
        int rt = copyNode(L);
17
        rson(rt) = merge(rson(rt),R);
18
        pushup(rt);
19
        return rt;
20
    }
21
    else
22
    {
23
        int rt = copyNode(R);
24
        lson(rt) = merge(L,lson(rt));
25
        pushup(rt);
26
        return rt;
27
    }
28
}
29
inline void splitVal(int rt,int val,int &L,int &R)
30
{
31
    if(!rt)
32
    {
33
        L = R = 0;
34
        return ;
35
    }
36
    if(tree[rt].val <= val)
37
    {
38
        L = copyNode(rt);
39
        splitVal(rson(L),val,rson(L),R);
40
        pushup(L);
41
    }
42
    else
43
    {
44
        R = copyNode(rt);
45
        splitVal(lson(R),val,L,lson(R));
46
        pushup(R);
47
    }
48
}

如果空间实在吃紧，可以考虑直接重构整棵树。

Thanks for reading!

数据结构Part 3

2025 1月 22 周三

2296 字 · 13 分钟

算法学习笔记 OI 数据结构