无旋转 Treap (FHQ-Treap)

FHQ-Treap（由中国清华大学范浩强同学发明并推广）是一种无需执行任何旋转操作的平衡二叉搜索树。它将二叉搜索树（BST）性质与堆（Heap）的随机优先级结合，所有操作仅基于两个极简的核心原语：split（分裂） 与 merge（合并）。

---

核心原语：分裂与合并

• split(u, val, &x, &y)：将以 \(u\) 为根的树分裂为两棵树 \(x\) 与 \(y\)，其中 \(x\) 中所有节点的权值 \(\le val\)，\(y\) 中所有节点的权值 \(> val\)。
• merge(&u, x, y)：将两棵树 \(x\) 与 \(y\) 合并为一棵新树 \(u\)。前提是 \(x\) 中所有权值 \(\le y\) 中所有权值。按节点的随机优先级（Priority）决定谁作为父节点，满足堆的性质。

由于无需维护复杂的旋转重平衡逻辑，FHQ-Treap 的代码极其短小精悍（约 60 行），并且天然支持可持久化以及区间操作（如区间翻转）。

---

1. 基础平衡树模版 (维护数值集合)

支持插入、删除、查询排名、查询第 \(k\) 小、前驱、后继。

#include <iostream>
#include <random>
#include <chrono>

struct FHQTreap {
    struct Node {
        int l = 0, r = 0;
        int val;
        int priority;
        int size = 1;
    };

    std::vector<Node> tree;
    int root = 0;
    std::mt19937 rnd;

    FHQTreap(int capacity = 100000) : rnd(13331) {
        tree.reserve(capacity + 5);
        tree.push_back({}); // 下标 0 作为虚拟空节点
    }

    int new_node(int val) {
        tree.push_back({0, 0, val, (int)rnd(), 1});
        return tree.size() - 1;
    }

    void push_up(int u) {
        if (!u) return;
        tree[u].size = 1 + tree[tree[u].l].size + tree[tree[u].r].size;
    }

    // 按权值分裂: <= val 的分到 x, > val 的分到 y
    void split(int u, int val, int &x, int &y) {
        if (!u) {
            x = y = 0;
            return;
        }
        if (tree[u].val <= val) {
            x = u;
            split(tree[u].r, val, tree[u].r, y);
        } else {
            y = u;
            split(tree[u].l, val, x, tree[u].l);
        }
        push_up(u);
    }

    // 合并: 假定 x 中所有权值 <= y 中所有权值
    int merge(int x, int y) {
        if (!x || !y) return x ? x : y;
        if (tree[x].priority < tree[y].priority) {
            tree[x].r = merge(tree[x].r, y);
            push_up(x);
            return x;
        } else {
            tree[y].l = merge(x, tree[y].l);
            push_up(y);
            return y;
        }
    }

    // 插入数值
    void insert(int val) {
        int x, y;
        split(root, val, x, y);
        root = merge(merge(x, new_node(val)), y);
    }

    // 删除单次出现的数值 val
    void erase(int val) {
        int x, y, z;
        split(root, val, x, z);
        split(x, val - 1, x, y);
        if (y) {
            // 删除 y 的根节点, 合并左右子树
            y = merge(tree[y].l, tree[y].r);
        }
        root = merge(merge(x, y), z);
    }

    // 查询 val 的排名 (小于 val 的元素个数 + 1)
    int rank(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int ans = tree[x].size + 1;
        root = merge(x, y);
        return ans;
    }

    // 查询排名第 k 的数值 (1-indexed)
    int kth(int k) {
        int cur = root;
        while (cur) {
            int left_sz = tree[tree[cur].l].size;
            if (k <= left_sz) {
                cur = tree[cur].l;
            } else if (k == left_sz + 1) {
                return tree[cur].val;
            } else {
                k -= left_sz + 1;
                cur = tree[cur].r;
            }
        }
        return -1;
    }

    // 前驱: 小于 val 的最大值
    int prev(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int cur = x;
        while (tree[cur].r) cur = tree[cur].r;
        int ans = tree[cur].val;
        root = merge(x, y);
        return ans;
    }

    // 后继: 大于 val 的最小值
    int next(int val) {
        int x, y;
        split(root, val, x, y);
        int cur = y;
        while (tree[cur].l) cur = tree[cur].l;
        int ans = tree[cur].val;
        root = merge(x, y);
        return ans;
    }
};

---

2. 文艺平衡树模版 (按大小分裂与区间翻转)

将 split 改为按子树大小分裂，并引入线段树般的懒标记（lazy tag），即可替代 Splay 完成区间反转、区间移动等序列操作（时间复杂度 \(\mathcal{O}((n + m) \log n)\)）。

struct IntervalTreap {
    struct Node {
        int l = 0, r = 0;
        int val;
        int priority;
        int size = 1;
        bool rev = false; // 区间翻转懒标记
    };

    std::vector<Node> tree;
    int root = 0;
    std::mt19937 rnd;

    IntervalTreap() : rnd(13331) { tree.push_back({}); }

    int new_node(int val) {
        tree.push_back({0, 0, val, (int)rnd(), 1, false});
        return tree.size() - 1;
    }

    void push_up(int u) {
        if (u) tree[u].size = 1 + tree[tree[u].l].size + tree[tree[u].r].size;
    }

    void push_down(int u) {
        if (u && tree[u].rev) {
            std::swap(tree[u].l, tree[u].r);
            if (tree[u].l) tree[tree[u].l].rev ^= 1;
            if (tree[u].r) tree[tree[u].r].rev ^= 1;
            tree[u].rev = false;
        }
    }

    // 按大小分裂: 将前 k 个元素分裂到 x, 其余分裂到 y
    void split(int u, int k, int &x, int &y) {
        if (!u) {
            x = y = 0;
            return;
        }
        push_down(u);
        int left_sz = tree[tree[u].l].size;
        if (k <= left_sz) {
            y = u;
            split(tree[u].l, k, x, tree[u].l);
        } else {
            x = u;
            split(tree[u].r, k - left_sz - 1, tree[u].r, y);
        }
        push_up(u);
    }

    int merge(int x, int y) {
        if (!x || !y) return x ? x : y;
        if (tree[x].priority < tree[y].priority) {
            push_down(x);
            tree[x].r = merge(tree[x].r, y);
            push_up(x);
            return x;
        } else {
            push_down(y);
            tree[y].l = merge(x, tree[y].l);
            push_up(y);
            return y;
        }
    }

    // 对区间 [l, r] 进行整体翻转 (1-indexed)
    void reverse(int l, int r) {
        int x, y, z;
        split(root, r, x, z);
        split(x, l - 1, x, y);
        tree[y].rev ^= 1; // 给区间打上翻转标记
        root = merge(merge(x, y), z);
    }

    // 中序遍历输出序列
    void print(int u) {
        if (!u) return;
        push_down(u);
        print(tree[u].l);
        std::cout << tree[u].val << " ";
        print(tree[u].r);
    }
};