题解：P3835 【模板】可持久化平衡树

xuanfeng101 · 2025-06-24 15:48:19 · 题解

前言

一篇用数组实现的较为清晰的 FHQ-Treap 题解，~~主要是看不懂指针题解~~。

题解

首先，我们需要了解可持久化平衡树的 FHQ 版本，当然不会也没有关系，接下来是解答。

对于可持久化这一名词，我们知道，就是继承之前用过的节点，只需要加入新的节点即可，根据平衡树性质，我们不难知道每次操作时空都是 O(\log n) 的，还是很优雅的，所以可持久化版本多的就是一个复制操作，即

int clone(int x)
{
    tr[ ++ idx] = tr[x];
    return idx;
}

然后在每次修改时调用这个函数，所有操作都用复制版本即可，那么如果你很熟练使用 FHQ-treap 的话本题就解完了，如果不熟悉我还是简单介绍一下具体细节。

首先就是两个底层函数 \operatorname{split} 和 \operatorname{merge}，第一个分裂函数代表的是将平衡树以一个值 v 划分为两个子树一个小于等于 v 一个大于 v，第二个合并函数是按 key 值，也就是按堆性质，将两个子树合并，具体实现如下：

void split(int u, int v, int& x, int& y)
{
    if (!u)
    {
        x = y = 0;
        return;
    }
    if (tr[u].v <= v)
    {
        x = clone(u);
        split(tr[x].r, v, tr[x].r, y);
        pushup(x);
    }
    else 
    {
        y = clone(u);
        split(tr[y].l, v, x, tr[y].l);
        pushup(y);
    }
}

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (tr[x].k <= tr[y].k)
    {
        x = clone(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else 
    {
        y = clone(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

仅仅只需要调用四次 clone 即可完成可持久化，也就是每次把需要分裂或在合并的点拷贝下来，用另一个新点代替即可。

再就是具体的每个操作：

加点。只需要按照 v 分裂子树，然后将新点与左树合并再与右子树合并。
删点。同理先按 v 分裂子树，再按 v - 1 分裂子树，根据我们分裂的原理可知，当前有一个子树的顶点权值为 v，那么我们先合并该点的两个子树，再与另外两个子树合并就巧妙的删除了。
排名。还是分裂子树，然后查询左子树的 sz + 1。
查询数。类似主席树方式，每次递归一侧查询。
查询前驱。我们分裂子树，然后调用 4 查询左子树最后一个点。
查询后驱。我们同样分裂子树，然后调用 4 查询右儿子的第一个点。

时间复杂度

O(n \log n)

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, INF = (1 << 31) - 1;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, rt[N], idx;
struct Node
{
    int l, r, v, k, sz;
}tr[N];

void pushup(int u)
{
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
}

int clone(int x)
{
    tr[ ++ idx] = tr[x];
    return idx;
}

void split(int u, int v, int& x, int& y)
{
    if (!u)
    {
        x = y = 0;
        return;
    }
    if (tr[u].v <= v)
    {
        x = clone(u);
        split(tr[x].r, v, tr[x].r, y);
        pushup(x);
    }
    else 
    {
        y = clone(u);
        split(tr[y].l, v, x, tr[y].l);
        pushup(y);
    }
}

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (tr[x].k <= tr[y].k)
    {
        x = clone(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else 
    {
        y = clone(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

int x, y, z;

int insert(int u, int v)
{
    int p = ++ idx;
    tr[p] = {0, 0, v, (int)rnd(), 1};
    split(u, v, x, y);
    return merge(merge(x, p), y);
}

int del(int u, int v)
{
    split(u, v, x, y);
    split(x, v - 1, x, z);
    if (z) z = merge(tr[z].l, tr[z].r);
    return merge(merge(x, z), y);
}

int get_rank(int u, int v)
{
    split(u, v - 1, x, y);
    int res = tr[x].sz + 1;
    merge(x, y);
    return res;
}

int kth(int u, int k)
{
    if (tr[tr[u].l].sz >= k) return kth(tr[u].l, k);
    else if (tr[tr[u].l].sz + 1 == k) return tr[u].v;
    return kth(tr[u].r, k - tr[tr[u].l].sz - 1);
}

int get_pre(int u, int v)
{
    split(u, v - 1, x, y);
    int res = -INF;
    if (x) res = kth(x, tr[x].sz);
    merge(x, y);
    return res;
}

int get_con(int u, int v)
{
    split(u, v, x, y);
    int res = INF;
    if (y) res = kth(y, 1);
    merge(x, y);
    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int pre, op, v;
        cin >> pre >> op >> v;
        rt[i] = rt[pre];
        if (op == 1) rt[i] = insert(rt[pre], v);
        else if (op == 2) rt[i] = del(rt[pre], v);
        else if (op == 3) cout << get_rank(rt[pre], v) << endl;
        else if (op == 4) cout << kth(rt[pre], v) << endl;
        else if (op == 5) cout << get_pre(rt[pre], v) << endl;
        else cout << get_con(rt[pre], v) << endl;
    }    
    return 0;
}