笛卡尔树¶

概述¶

笛卡尔树同时满足二叉搜索树（按键值）和堆（按优先级）的性质，常用于RMQ问题和构建Treap。

笛卡尔树特点¶

BST性质：中序遍历按键有序
堆性质：父节点优先级优于子节点
唯一性：键值互不相同时唯一
线性构建：可O(n)时间构建

数据结构¶

C
typedef struct CartesianNode {
    int key;
    int value;
    struct CartesianNode *left;
    struct CartesianNode *right;
    struct CartesianNode *parent;
} CartesianNode;

typedef struct {
    CartesianNode *root;
} CartesianTree;

创建节点¶

C
CartesianNode* createCartesianNode(int key, int value) {
    CartesianNode *node = (CartesianNode*)malloc(sizeof(CartesianNode));
    node->key = key;
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}

CartesianTree* createCartesianTree() {
    CartesianTree *tree = (CartesianTree*)malloc(sizeof(CartesianTree));
    tree->root = NULL;
    return tree;
}

构建笛卡尔树（单调栈）¶

C
CartesianTree* buildCartesianTree(int keys[], int values[], int n) {
    CartesianTree *tree = createCartesianTree();
    
    if (n == 0) return tree;
    
    CartesianNode **stack = (CartesianNode**)malloc(sizeof(CartesianNode*) * n);
    int top = -1;
    
    for (int i = 0; i < n; i++) {
        CartesianNode *node = createCartesianNode(keys[i], values[i]);
        CartesianNode *last = NULL;
        
        while (top >= 0 && stack[top]->value > values[i]) {
            last = stack[top--];
        }
        
        node->left = last;
        if (last) last->parent = node;
        
        if (top >= 0) {
            stack[top]->right = node;
            node->parent = stack[top];
        }
        
        stack[++top] = node;
    }
    
    tree->root = stack[0];
    
    while (tree->root->parent != NULL) {
        tree->root = tree->root->parent;
    }
    
    free(stack);
    return tree;
}

RMQ查询¶

C
int queryRMQ(CartesianNode *root, int l, int r) {
    if (root == NULL) return INT_MAX;
    
    if (root->key < l) {
        return queryRMQ(root->right, l, r);
    } else if (root->key > r) {
        return queryRMQ(root->left, l, r);
    } else {
        return root->value;
    }
}

LCA查询¶

C
CartesianNode* lcaCartesian(CartesianNode *root, int l, int r) {
    if (root == NULL) return NULL;
    
    if (root->key < l) {
        return lcaCartesian(root->right, l, r);
    } else if (root->key > r) {
        return lcaCartesian(root->left, l, r);
    }
    
    return root;
}

中序遍历¶

C
void inorderCartesian(CartesianNode *root, int result[], int *index) {
    if (root == NULL) return;
    
    inorderCartesian(root->left, result, index);
    result[(*index)++] = root->value;
    inorderCartesian(root->right, result, index);
}

C++ 实现¶

C++
#include <vector>
#include <stack>
#include <algorithm>

class CartesianTree {
private:
    struct Node {
        int key, value;
        Node *left, *right, *parent;
        Node(int k, int v) : key(k), value(v), 
                            left(nullptr), right(nullptr), parent(nullptr) {}
    };
    
    Node *root;
    
public:
    CartesianTree() : root(nullptr) {}
    
    void build(const std::vector<int>& keys, const std::vector<int>& values) {
        int n = keys.size();
        if (n == 0) return;
        
        std::stack<Node*> st;
        
        for (int i = 0; i < n; i++) {
            Node *node = new Node(keys[i], values[i]);
            Node *last = nullptr;
            
            while (!st.empty() && st.top()->value > values[i]) {
                last = st.top();
                st.pop();
            }
            
            node->left = last;
            if (last) last->parent = node;
            
            if (!st.empty()) {
                st.top()->right = node;
                node->parent = st.top();
            }
            
            st.push(node);
        }
        
        root = st.top();
        while (root->parent) root = root->parent;
    }
    
    int rmq(int l, int r) {
        Node *curr = root;
        
        while (curr) {
            if (curr->key < l) {
                curr = curr->right;
            } else if (curr->key > r) {
                curr = curr->left;
            } else {
                return curr->value;
            }
        }
        
        return INT_MAX;
    }
    
    std::vector<int> inorder() {
        std::vector<int> result;
        inorderHelper(root, result);
        return result;
    }
    
private:
    void inorderHelper(Node *node, std::vector<int>& result) {
        if (!node) return;
        inorderHelper(node->left, result);
        result.push_back(node->value);
        inorderHelper(node->right, result);
    }
};

笛卡尔树与RMQ¶

笛卡尔树将RMQ问题转化为LCA问题： - 数组元素值作为堆优先级 - 数组下标作为BST键值 - 区间[l,r]的最小值 = lca(l,r)的值

笛卡尔树与Treap¶

如果优先级随机，笛卡尔树就是Treap： - 期望高度O(log n) - 期望操作时间O(log n)

时间复杂度¶

操作	时间复杂度
构建	O(n)
RMQ	O(n) 最坏
LCA	O(n) 最坏
中序遍历	O(n)

应用场景¶

RMQ问题：区间最值查询
构建Treap：快速构建
字符串算法：后缀数组构建
虚树构建：LCA相关

参考资料¶

Vuillemin (1980) 笛卡尔树论文
《数据结构与算法分析》