FHQ-Treap超详细教程

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

数据结构定义

CPP

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) { /*...*/ }
};

$lc/rc$ : 左右子节点索引。
$pri$ : 随机优先级，用于维护堆性质。
$siz$ : 子树大小。
$val$ : 节点存储的值。
$tot$ : 节点总数， $rt$ : 根节点。
$l/r/tmp$ : 临时变量用于 Split 和 Merge。

核心操作

1. 分裂（Split）

CPP

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）

CPP

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）

CPP

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

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

2. 删除（Delete）

CPP

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）

CPP

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

4. 前驱/后继

CPP

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 操作实现高效动态维护有序集合，结合全局偏移量优化批量更新，适用于需要频繁插入、删除和查询的场景。

FHQ-Treap超详细教程

文章操作

数据结构定义

核心操作

1. 分裂（Split）

2. 合并（Merge）

常用操作

1. 插入（Insert）

2. 删除（Delete）

3. 查询排名（Rank）

4. 前驱/后继

主函数逻辑

关键技巧

总结

相关推荐

评论

FHQ-Treap超详细教程