洛谷P3369题解：Treap动态数据结构详解与代码实现
5个月前 (07-23)
一、题目解读
洛谷P3369题要求处理动态区间内的数据操作，涉及插入、删除及查询等。题目难点在于维护数据的动态平衡与高效查找，传统数据结构难以满足其性能需求。因此，需采用具有随机化平衡特性的Treap（树堆）来应对。
二、解题思路
采用Treap（树堆）结构，结合二叉搜索树的有序性与堆的优先级特性。通过随机生成节点优先级，在插入或删除时自动调整树形结构，避免极端不平衡情况。核心思路为：利用随机优先级驱动旋转操作，确保树高logN级别，从而维持整体操作O(logN)复杂度。
三、解题步骤
1. 构建Treap基础框架：定义节点结构（值、大小、计数、优先级、左右子树），初始化随机优先级避免固定规律。
2. 旋转操作优化平衡：通过左旋/右旋调整子树位置，依据优先级判断旋转条件（子节点优先级更高时触发）。
3. 动态维护：
○ 插入：递归至对应位置，更新节点计数与大小，必要时旋转；
○ 删除：若重复值则减计数，否则递归处理并合并子树，保证删除后仍平衡。
4. 更新机制：每次操作后自底向上更新节点size（子树+自身）。
四、代码与注释
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
const int INF = 1e8; // 处理大数值范围，避免优先级重复
struct Node {
int val, size, cnt; // 值、子树大小、重复计数
int priority; // 随机优先级
Node *l, *r; // 左右子树
Node(int v) : val(v), size(1), cnt(1), l(nullptr), r(nullptr) {
priority = rand() % INF; // 初始化随机优先级
}
};
class Treap {
private:
Node *root;
void update(Node *node) { // 更新节点信息
if(!node) return;
node->size = node->cnt; // 初始大小为自身
if(node->l) node->size += node->l->size; // 累加左子树
if(node->r) node->size += node->r->size; // 累加右子树
}
void rotateLeft(Node *&node) { // 左旋（右子树优先级高时）
Node *temp = node->r;
node->r = temp->l; // 调整子树连接
temp->l = node;
update(node); // 更新受影响节点信息
update(temp);
node = temp;
}
void rotateRight(Node *&node) { // 右旋（左子树优先级高时）
// 对称处理，逻辑同左旋
}
void insert(Node *&node, int val) {
if(!node) { // 空节点直接创建
node = new Node(val);
return;
}
if(val == node->val) { // 重复值，计数+1
node->cnt++;
} else if(val < node->val) {
insert(node->l, val); // 递归左子树
if(node->l->priority > node->priority) // 左子树优先级高，右旋
rotateRight(node);
} else {
// 递归右子树，优先级高则左旋
}
update(node); // 操作后更新节点
}
void remove(Node *&node, int val) {
if(!node) return;
if(val < node->val) {
remove(node->l, val);
} else if(val > node->val) {
remove(node->r, val);
} else {
if(node->cnt > 1) { // 重复值，直接减计数
node->cnt--;
} else { // 删除节点
if(!node->l ||!node->r) { // 无子树或仅单侧子树
Node *temp = node->l? node->l : node->r; // 合并子树
delete node; // 释放原节点
node = temp; // 更新根指针
} else { // 双侧子树，递归删除
if(node->l->priority > node->r->priority) { // 左子树优先级高，右旋后递归删右子树
rotateRight(node);
remove(node->r, val);
} else {
// 对称处理，左旋后递归删左子树
rotateLeft(node);
remove(node->l, val);
}
}
}
}
if(node) update(node);
}
int getRank(Node *node, int val) {
if(!node) return 0;
if(val < node->val) return getRank(node->l, val);
int leftSize = node->l ? node->l->size : 0;
if(val == node->val) return leftSize + 1;
return leftSize + node->cnt + getRank(node->r, val);
}
int getValue(Node *node, int rank) {
if(!node) return INF;
int leftSize = node->l ? node->l->size : 0;
if(rank <= leftSize) return getValue(node->l, rank);
if(rank <= leftSize + node->cnt) return node->val;
return getValue(node->r, rank - leftSize - node->cnt);
}
int getPre(Node *node, int val) {
if(!node) return -INF;
if(node->val >= val) return getPre(node->l, val);
return max(node->val, getPre(node->r, val));
}
int getNext(Node *node, int val) {
if(!node) return INF;
if(node->val <= val) return getNext(node->r, val);
return min(node->val, getNext(node->l, val));
}
public:
Treap() : root(nullptr) { srand(time(0)); }
void insert(int val) { insert(root, val); }
void remove(int val) { remove(root, val); }
int getRank(int val) { return getRank(root, val); }
int getValue(int rank) { return getValue(root, rank); }
int getPre(int val) { return getPre(root, val); }
int getNext(int val) { return getNext(root, val); }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Treap treap;
int n, opt, x;
cin >> n;
while(n--) {
cin >> opt >> x;
switch(opt) {
case 1: treap.insert(x); break;
case 2: treap.remove(x); break;
case 3: cout << treap.getRank(x) << '\n'; break;
case 4: cout << treap.getValue(x) << '\n'; break;
case 5: cout << treap.getPre(x) << '\n'; break;
case 6: cout << treap.getNext(x) << '\n'; break;
}
}
return 0;
}五、总结
Treap通过随机化优先级与旋转机制，巧妙结合了BST的查询效率与堆的平衡性，适用于动态区间操作的场景。其时间复杂度稳定在O(logN)，且无需复杂的手动平衡调整，是解决此类问题的经典方案。理解其旋转逻辑与递归设计，对提升动态数据结构实践能力具有重要意义。
原创内容 转载请注明出处
