【模板】普通平衡树题解

题目描述

维护一个可重集合，支持以下种操作：

插入
删除一个（若有多个只删一个）
查询的排名（排名定义为比小的数的个数，若有多个相同的输出最小的排名）
查询排名为的数
求的前驱（小于的最大数）
求的后继（大于的最小数）

操作总数，数的范围。

解法分析

这是一道平衡树的模板题。常用的数据结构有：

· Treap（树堆）：每个节点随机赋予优先级，通过旋转维护堆性质，期望。 · Splay（伸展树）：每次操作后将节点旋转到根，均摊。 · FHQ Treap（无旋 Treap）：通过分裂与合并实现所有操作，代码简洁，易于理解。 · 树状数组 / 线段树：先将所有可能出现的离散化，然后使用权值线段树维护，因为操作只有插入删除和排名查询，可以做到（为离散化后值域大小）。但需要处理重复元素（每个叶子节点记录个数即可），且前驱后继可通过查询排名转化。

由于只有，且的范围较大但操作数有限，离散化后值域大小最多，因此权值线段树或树状数组也是可行的。

下面以 FHQ Treap 为例讲解。

FHQ Treap 实现思路

FHQ Treap 的核心操作是两个：

· split(root, key)：将树按照键值和分裂成两棵树。 · merge(a, b)：将两棵树合并（保证中所有节点键值中所有节点键值），并按照优先级维护堆性质。

对于每个节点，需要存储：

· val：键值 · pri：随机优先级 · siz：子树大小（用于排名查询） · cnt：该键值出现的次数（支持重复元素） · lch, rch：左右孩子

操作实现

插入按分裂为（）和（），再按将分裂为（）和（的部分）。若为空，则新建节点；否则将对应节点的 cnt++ 并更新 siz。最后依次合并、、。
删除类似插入，找到即的子树。若 cnt > 1 则减一，否则直接丢弃该节点。然后合并。
查询的排名按分裂，左树的大小即为比小的个数，排名为 size(L) + 1。记得合并回去。
查询排名为的数从根开始递归：若左子树大小则去左子树；若左子树大小则返回当前节点的值；否则减去左子树大小后去右子树。
求前驱按分裂，左树中的最大值即为前驱。可以在左树中一直向右走。
求后继按分裂，右树中的最小值即为后继。可以在右树中一直向左走。

注意：每次操作后要检查是否需要合并回原树，避免树的结构被破坏。

复杂度

· 时间复杂度：所有操作均为期望。 · 空间复杂度：。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

struct Node {
    int val, pri, siz, cnt;
    int lch, rch;
} tr[MAXN];
int root, tot;

int newNode(int v) {
    tr[++tot].val = v;
    tr[tot].pri = rand();
    tr[tot].siz = tr[tot].cnt = 1;
    tr[tot].lch = tr[tot].rch = 0;
    return tot;
}

void pushup(int u) {
    tr[u].siz = tr[tr[u].lch].siz + tr[tr[u].rch].siz + tr[u].cnt;
}

void split(int u, int key, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }
    if (tr[u].val <= key) {
        x = u;
        split(tr[u].rch, key, tr[u].rch, y);
    } else {
        y = u;
        split(tr[u].lch, key, x, tr[u].lch);
    }
    pushup(u);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].pri < tr[y].pri) {
        tr[x].rch = merge(tr[x].rch, y);
        pushup(x);
        return x;
    } else {
        tr[y].lch = merge(x, tr[y].lch);
        pushup(y);
        return y;
    }
}

void insert(int v) {
    int L, R;
    split(root, v, L, R);
    int L1, L2;
    split(L, v - 1, L1, L2);
    if (!L2) {
        L2 = newNode(v);
    } else {
        tr[L2].cnt++;
        pushup(L2);
    }
    root = merge(merge(L1, L2), R);
}

void erase(int v) {
    int L, R;
    split(root, v, L, R);
    int L1, L2;
    split(L, v - 1, L1, L2);
    if (tr[L2].cnt > 1) {
        tr[L2].cnt--;
        pushup(L2);
        root = merge(merge(L1, L2), R);
    } else {
        root = merge(L1, R);
    }
}

int getRank(int v) {
    int L, R;
    split(root, v - 1, L, R);
    int ans = tr[L].siz + 1;
    root = merge(L, R);
    return ans;
}

int kth(int u, int k) {
    if (tr[tr[u].lch].siz >= k) return kth(tr[u].lch, k);
    if (tr[tr[u].lch].siz + tr[u].cnt >= k) return tr[u].val;
    return kth(tr[u].rch, k - tr[tr[u].lch].siz - tr[u].cnt);
}

int pre(int v) {
    int L, R;
    split(root, v - 1, L, R);
    int u = L;
    while (tr[u].rch) u = tr[u].rch;
    int ans = tr[u].val;
    root = merge(L, R);
    return ans;
}

int nxt(int v) {
    int L, R;
    split(root, v, L, R);
    int u = R;
    while (tr[u].lch) u = tr[u].lch;
    int ans = tr[u].val;
    root = merge(L, R);
    return ans;
}

int main() {
    srand(time(0));
    int n;
    scanf("%d", &n);
    while (n--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(x);
        else if (opt == 2) erase(x);
        else if (opt == 3) printf("%d\n", getRank(x));
        else if (opt == 4) printf("%d\n", kth(root, x));
        else if (opt == 5) printf("%d\n", pre(x));
        else printf("%d\n", nxt(x));
    }
    return 0;
}

其他解法

· Treap（旋转版）：同样使用随机优先级，通过左旋右旋维持堆性质，实现类似。 · Splay：每次操作后伸展，灵活但代码稍长。 · 权值线段树：离线离散化后，将数值看作下标，插入/删除对应叶子节点加减，排名查询可以线段树上二分，前驱后继通过查询区间最值实现。

总结

平衡树是维护有序序列的有力工具。本题要求掌握常见平衡树的基本操作，是许多更复杂数据结构（如可持久化平衡树、区间翻转等）的基础。建议读者至少实现一种平衡树，并深刻理解其核心原理。

【模板】普通平衡树 题解

暂无评论