洛谷P3369题解：Treap动态数据结构详解与代码实现

一、题目解读

洛谷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)，且无需复杂的手动平衡调整，是解决此类问题的经典方案。理解其旋转逻辑与递归设计，对提升动态数据结构实践能力具有重要意义。