代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include "bits/stdc++.h"
using namespace std;

struct FHQTreap {
    // 无旋Treap：满足BST性质(val)和堆性质(priority)
    struct Node {
        int val;
        int size = 0;
        int priority;  // 随机优先级
        Node *left, *right;
        Node(int val) : val(val), priority(rand()), left(NULL), right(NULL), size(1) {}
        Node(int val, int priority) : val(val), priority(priority), left(NULL), right(NULL), size(1) {}
    };

    bool cmp(int a, int b) { return a <= b; }  // 自定义比较函数，满足BST性质
    Node *root;

    FHQTreap() : root(NULL) { srand((unsigned)time(nullptr)); }

    // 更新节点size
    void update(Node *root) {
        if (!root) return;
        root->size = 1;
        if (root->left) root->size += root->left->size;
        if (root->right) root->size += root->right->size;
    }

    // 合并两棵树a,b为root，满足BST和堆性质
    void merge(Node *&root, Node *a, Node *b) {
        if (!a || !b) {  // 存在空树，直接返回
            root = a ? a : b;
        } else {
            if (a->priority > b->priority) {
                root = a;
                merge(a->right, a->right, b);
            } else {
                root = b;
                merge(b->left, a, b->left);
            }
        }

        update(root);
    }

    // 按val拆分root为a,b，a中所有val <= val，b中所有val > val
    void split(Node *root, Node *&a, Node *&b, int val) {
        if (!root) {
            a = b = NULL;
            return;
        }

        if (cmp(root->val, val)) {
            a = root;
            split(root->right, a->right, b, val);
        } else {
            b = root;
            split(root->left, a, b->left, val);
        }

        update(root);
    }

    // 插入val
    void insert(int val) {
        Node *a, *b;
        split(root, a, b, val);
        merge(a, a, new Node(val));
        merge(root, a, b);
    }

    // 删除val（只删除一个）
    void erase(int val) {
        Node *a, *b, *c;
        split(root, a, b, val);
        split(a, a, c, val - 1);
        if (c) {
            // 删除c根节点，合并其左右子树
            merge(a, a, c->left);
            merge(a, a, c->right);
            delete c;  // 防止内存泄漏
        }
        merge(root, a, b);
    }

    // 返回val的排名（比val小的元素个数+1）
    int order_of_key(int val) {
        Node *a, *b;
        split(root, a, b, val - 1);
        int res = (a ? a->size : 0) + 1;
        merge(root, a, b);
        return res;
    }

    // 查询第k小元素，k从1开始，越界返回-1
    int find_by_order(int k) { return kth_query(root, k); }

    int kth_query(Node *root, int k) {
        if (!root) return -1;
        int leftsize = root->left ? root->left->size : 0;
        if (k <= leftsize) return kth_query(root->left, k);  // 左子树中第k小
        if (k == leftsize + 1) return root->val;             // 找到第k小元素
        return kth_query(root->right, k - leftsize - 1);     // 右子树中第k-leftsize-1小
    }

    // 查找val是否存在
    bool find(int val) {
        Node *a, *b;
        split(root, a, b, val);
        bool res = (a && find_max(a) == val);
        merge(root, a, b);
        return res;
    }

    // val的前驱（小于val的最大元素），不存在返回-1
    int predecessor(int val) {
        Node *a, *b;
        split(root, a, b, val - 1);
        int res = find_max(a);
        merge(root, a, b);
        return res;
    }

    // val的后继（大于val的最小元素），不存在返回-1
    int successor(int val) {
        Node *a, *b;
        split(root, a, b, val);
        int res = find_min(b);
        merge(root, a, b);
        return res;
    }

    // 中序打印
    void print(Node *root) {
        if (!root) return;
        print(root->left);
        cout << root->val << " ";
        print(root->right);
    }

    int find_max(Node *root) {
        if (!root) return -1;
        while (root->right) root = root->right;
        return root->val;
    }

    int find_min(Node *root) {
        if (!root) return -1;
        while (root->left) root = root->left;
        return root->val;
    }
};

FHQ_Treap (>^ω^<)喵#

FHQTreap 简介 ✨

FHQTreap（无旋 Treap）是一种基于随机优先级的平衡二叉搜索树，兼具二叉搜索树和堆的性质。
它避免了传统 Treap 中通过旋转调整平衡的复杂操作，转而采用“分裂（split）”和“合并（merge）”两大核心操作来维护树结构的平衡。
这种设计极大简化了实现过程，且依然保证了插入、删除、查询等操作在平均 O(log n) 时间复杂度内完成。
因此，FHQTreap 非常适合算法竞赛、在线处理动态区间与序列问题等场景，具有高效与优雅兼备的特性 (｡•̀ᴗ-)✧ (≧▽≦)✧

主要特点 🌟

  • 🌀 无旋转设计：摒弃传统 Treap 中繁琐的旋转操作，逻辑清晰、代码简洁 (ง •̀_•́)ง
  • 🎲 基于随机优先级：通过随机生成的优先级保证树的平衡性，避免退化为链表 (๑˃ᴗ˂)ﻭ
  • 🔀 灵活的拆分与合并：通过 split 和 merge 操作，可以高效实现区间拆分、区间合并等复杂操作，拓展性强 (✿◠‿◠)
  • 🔍 支持多种查询功能：支持排名查询、按排名查找元素、前驱后继查找等丰富接口，满足多样需求 (＾▽＾)
  • 💻 应用广泛：常见于竞赛中动态维护有序集合、区间动态插入删除等问题，且代码易于移植和改造 (≧◡≦)

主要接口与功能说明 🔧

  • ➕ insert(int val)
    插入元素 val 到树中，保持数据结构的平衡和有序性 (•̀ᴗ•́)و ̑̑

  • ❌ erase(int val)
    删除值为 val 的节点（若存在多个，仅删除一个），保持树的完整性 (ง •̀_•́)ง

  • 🔢 order_of_key(int val)
    查询值 val 在序列中的排名（即比 val 小的元素个数 + 1），可用于统计排序信息 (✧ω✧)

  • 🎯 find_by_order(int k)
    查询第 k 小的元素，k 从 1 开始计数；若 k 越界则返回 -1 (°ロ°)☝

  • 🔍 find(int val)
    判断值 val 是否存在于数据结构中，返回布尔结果 (⌐■_■)

  • ⬅️ predecessor(int val)
    查询严格小于 val 的最大元素（前驱），若无前驱则返回 -1 (╯︵╰,)

  • ➡️ successor(int val)
    查询严格大于 val 的最小元素（后继），若无后继则返回 -1 (๑•́ ₃ •̀๑)

  • 🖨️ print(Node* root)
    中序遍历并打印树中所有元素，主要用于调试和验证树结构 (｡♥‿♥｡)

使用说明 📝

  1. 🎲 初始化：创建 FHQTreap 对象时，内部自动设定随机种子，保证随机优先级的均匀分布。
  2. ➕❌ 插入与删除：通过 insert 和 erase 函数动态修改树，结构自动调整，保持平衡 (•̀ᴗ•́)و ̑̑
  3. 🔢🔍 查询操作：利用排名和前驱后继等接口，实现快速定位和统计功能 (＾▽＾)
  4. 🔧 灵活扩展：通过修改比较函数或节点内容，可以方便地扩展到多种场景，如区间修改、区间查询等 (✿◠‿◠)

典型应用场景 🚀

  • 🗃️ 动态维护有序集合，支持快速插入、删除、排名查询 (⌒▽⌒)
  • 📊 在线计算元素排名，统计区间内元素数量 ( •̀ ω •́ )✧
  • 🔀 处理动态区间合并、拆分问题，如动态开区间、区间覆盖问题 (＾◡＾)っ
  • 🏆 竞赛中对序列元素的动态管理，如动态 LIS、动态逆序对等问题 (ง •̀_•́)ง

总结 🎉

FHQTreap 以其简洁的无旋设计和强大的拆分合并操作，成为算法竞赛中常用的高效数据结构之一。
掌握其核心思想和接口使用，可以极大提升动态数据结构相关问题的处理能力 (｡◕‿◕｡)✧٩(ˊᗜˋ*)و