FHQ-Treap超详细教程

Him_shu · 2025-04-12 16:52:09 · 算法·理论

FHQ Treap 是一种基于分裂（Split）和合并（Merge）操作的无旋平衡树，其核心思想是通过随机优先级维护树的平衡性。以下是对代码的详细讲解：

数据结构定义

struct Treap {
    int lc[N], rc[N], pri[N], siz[N], tot, rt;
    ll val[N];
    int l, r, tmp;

    // 创建新节点
    int New(ll x) {
        tot++;
        val[tot] = x;
        pri[tot] = Rand(); // 随机优先级
        siz[tot] = 1;
        return tot;
    }

    // 更新子树大小
    void pu(int x) { siz[x] = siz[lc[x]] + siz[rc[x]] + 1; }

    // 分裂操作
    void Split(int id, int k, int &x, int &y) { /*...*/ }

    // 合并操作
    int Merge(int x, int y) { /*...*/ }

    // 插入、删除、查询等操作
    void insert(int x) { /*...*/ }
    void del(int x) { /*...*/ }
    ll Rank(int x) { /*...*/ }
    ll get_val(int x, ll k) { /*...*/ }
    ll get_pre(ll x) { /*...*/ }
    ll get_suf(int x) { /*...*/ }
};

核心操作

1. 分裂（Split）

void Split(int id, int k, int &x, int &y) {
    if (!id) { x = y = 0; return; }
    if (val[id] <= k)
        x = id, Split(rc[id], k, rc[id], y);
    else
        y = id, Split(lc[id], k, x, lc[id]);
    pu(id);
}

功能：将树分为两部分，x 子树的所有值 \le k，y 子树的所有值 >k。
递归逻辑：根据当前节点的值决定归属子树，递归处理左右子树。

2. 合并（Merge）

int Merge(int x, int y) {
    if (!x || !y) return x + y;
    if (pri[x] <= pri[y]) {
        rc[x] = Merge(rc[x], y);
        pu(x);
        return x;
    } else {
        lc[y] = Merge(x, lc[y]);
        pu(y);
        return y;
    }
}

功能：合并两棵树，保证优先级满足堆性质。
逻辑：优先级高的节点作为父节点，递归合并子树。

常用操作

1. 插入（Insert）

void insert(int x) {
    Split(rt, x - 1, l, r);    // 分裂为 <=x-1 和 >x-1
    rt = Merge(Merge(l, New(x)), r); // 新建节点并合并
}

步骤：将树分裂为两部分，插入新节点后合并。

2. 删除（Delete）

void del(int x) {
    Split(rt, x - 1, l, r);    // 分裂为 <=x-1 和 >x-1
    Split(r, x, tmp, r);       // 从 >x-1 中分裂出 ==x 的子树
    tmp = Merge(lc[tmp], rc[tmp]); // 合并 tmp 的左右子树（删除根）
    rt = Merge(Merge(l, tmp), r);
}

步骤：分裂出所有值为 x 的节点，合并其左右子树以删除根节点。

3. 查询排名（Rank）

ll Rank(int x) {
    Split(rt, x - 1, l, r);
    int ans = siz[l];          // <=x-1 的节点数即为排名
    rt = Merge(l, r);
    return ans;
}

4. 前驱/后继

ll get_pre(ll x) {
    Split(rt, x - 1, l, r);    // 分裂为 <=x-1 和 >x-1
    ll ans = get_val(l, siz[l]); // 左子树的最大值
    rt = Merge(l, r);
    return ans;
}

ll get_suf(int x) {
    Split(rt, x, l, r);        // 分裂为 <=x 和 >x
    ll ans = get_val(r, 1);    // 右子树的最小值
    rt = Merge(l, r);
    return ans;
}

主函数逻辑

插入：若工资 minv \le x，插入 x - sum（sum 为全局偏移量）。
加薪：更新全局偏移量 sum += x。
降薪：更新 sum -= x，删除所有实际工资 (val + sum) < minv 的节点。
查询：输出第 k 大的工资（需转换为当前偏移量）。

关键技巧

全局偏移量 sum：通过维护 sum 避免频繁修改所有节点值，插入时存储相对值 x - sum，查询时还原为 val + sum。
懒惰删除：在降薪操作时，通过不断查找并删除前驱节点，高效移除不符合条件的元素。

总结

FHQ Treap 通过 Split 和 Merge 操作实现高效动态维护有序集合，结合全局偏移量优化批量更新，适用于需要频繁插入、删除和查询的场景。