首页 » 技术分享 » FHQ Treap 总结

FHQ Treap 总结

　
评论关闭　834次浏览

【前言（一堆废话）】
目前 OI 竞赛中两大主流平衡树之一就是 FHQ Treap（另一个是 Splay）。
普通 BST 的中序遍历中，val 值构成一个单调递增的序列。
Treap 在 BST 的基础上，维护了一个 key 值，使其 val 满足 BST 性质，key 满足 Heap 性质。在维护 Heap 性质的同时，使 Treap 的树高期望是 log(n)。通常情况下，key 值是随机的。
普通的 Treap 通过旋转维护 Heap 性质，实现简单且性能优越，相关资料也很广泛，这里就不在赘述。
FHQ Treap，又称 非旋 Treap，函数式 Treap。由神犇FHQ首先提出（OrzOrzOrz）。函数式编程的思想，使其可以实现持久化。

【核心操作】
FHQ Treap 有两个核心操作，split 和 merge。
split 的作用是将一棵树分裂成两部分，其中左半部分的子树 size == k。
其实也可以按结点 val 值分裂，这样就可以完成普通平衡树的操作。

void split(int o, int k, int &x, int &y) { // 将根为 o 的树分裂成以 x, y 为根的两棵树，其中 x 的子树大小为 k
    if (!o) { x = y = 0; return; } // o 不存在, 返回
    int c = t[t[o].lc].size; // o 左子树大小
    push_down(o); // 先把维护的信息下推
    if (c < k) { // 左子树 size 不够，递归到右子树处理
        x = o; 
        split(t[o].rc, k - c - 1, t[o].rc, y);
    }
    else { // 左子树 size 以能满足要求，递归到左子树处理
        y = o;
        split(t[o].lc, k, x, t[o].lc);
    }
    push_up(o); // 分裂完成后，信息上推
}

merge 操作的作用是将两棵树合并，返回合并后的根节点

int merge(int x, int y) { // 合并以 x, y 为根的两棵树，返回合并后的根节点
    if (!x || !y) return x | y; // 其中一棵为空树，返回非空的树
    if (t[x].key < t[y].key) { // 维护小根堆
        push_down(x);
        t[x].rc = merge(t[x].rc, y); // 递归处理，注意要保证中序遍历 x 在 y 左边
        push_up(x);
        return x;
    }
    else {
        push_down(y);
        t[y].lc = merge(x, t[y].lc);
        push_up(y);
        return y;
    }
}

通过这两个操作可以完成任何 Splay 能够完成的操作。
例题：洛谷 P3391 【模板】文艺平衡树
每次 split 出 [1，l - 1]，[l，r]，[r + 1，n] s三个区间，再打上反转标记。

【其他操作】
父指针：通常情况下，FHQ Treap不用维护父指针。如果一定要维护也没问 题。只需在 push_up 函数中加上

if (lc) t[lc].fa = o; // 注意无左（右）子树的情况
if (rc) t[rc].fa = o;

在 split 后，将分裂出的子树父指针清空

t[u].fa = t[v].fa = 0; // 分裂出以 u, v 为根的子树

建树：最简单的，暴力插入建树

for (int i = 1; i <= n; i++) root = merge(root, new_node(i));

时间复杂度O(nlogn))，已经很优秀。但在某些时候会成为性能瓶颈。

考虑到 key 值满足笛卡尔树的性质，所以可以用同样的思路建树。
用单调栈维护树的最右链，注意要维护左右子树指针，同时 push_up。

int build(int *a, int k) { // 以 a[] 中 [1, k] 建树
    int root = 0;
    memset(s, 0, sizeof s); // 清空栈
    for (int i = 1, x, y; i <= k; ++i) {
        x = new_node(a[i]), y = 0;
        while (top && t[x].key < t[s[top]].key) { y = s[top--]; push_up(y); }
        s[++top] = x;
        t[x].lc = y;
        if (top) t[s[top - 1]].rc = x;
        if (top == 1) root = x; // 维护根结点
    }
    while (top) push_up(s[top--]);
    return root;
}

时间复杂度 O（n），与 Splay 建树持平

【优缺点】
优点：代码短，易实现。不用旋转。拓展性强。
缺点：作为 LCT 的辅助树时，时间复杂度比 Splay 多一个 log。

【可持久化】
等我学了在写。。。

【经典题目】
略。。。

转载自原文链接, 如需删除请联系管理员。

原文链接：FHQ Treap 总结，转载请注明来源！

赞 0