C++怎么实现一个笛卡尔树_C++数据结构与RMQ问题的高效解法-C++-PHP中文网

C++怎么实现一个笛卡尔树_C++数据结构与RMQ问题的高效解法

穿越時空

发布： 2025-11-24 13:10:02

原创

201人浏览过

笛卡尔树通过结合二叉搜索树和堆性质，将RMQ问题转化为LCA问题，利用单调栈在O(n)时间内构建，并配合DFS与稀疏表实现O(1)查询，适用于静态数据的高效区间最值查询。

c++怎么实现一个笛卡尔树_c++数据结构与rmq问题的高效解法

笛卡尔树（Cartesian Tree）是一种结合了二叉搜索树和堆性质的数据结构，常用于解决RMQ（Range Minimum/Maximum Query，区间最值查询）问题。通过将RMQ转化为LCA（Lowest Common Ancestor，最近公共祖先）问题，笛卡尔树能在线性预处理后实现O(1)查询，是C++中高效处理静态RMQ的重要手段。

笛卡尔树的定义与性质

笛卡尔树满足两个关键性质：

二叉搜索树性质：中序遍历结果等于原数组顺序。
最小堆性质：每个节点的值小于等于其子节点的值（最小笛卡尔树）。

构建完成后，原数组任意区间的最小值对应笛卡尔树中该区间对应节点的LCA。这使得RMQ问题可通过LCA求解。

线性时间构建笛卡尔树

利用单调栈可以在O(n)时间内完成构建。核心思路是维护一个值递增的栈，逐个插入元素并调整树结构。

立即学习“C++免费学习笔记（深入）”；

示例代码：

#include <vector>
#include <stack>
using namespace std;
<p>struct Node {
int val, idx;
Node<em> left, </em> right;
Node(int v, int i) : val(v), idx(i), left(nullptr), right(nullptr) {}
};</p><p>Node* buildCartesianTree(const vector<int>& arr) {
int n = arr.size();
if (n == 0) return nullptr;</p><pre class='brush:php;toolbar:false;'>vector<Node*> nodes;
for (int i = 0; i < n; ++i)
    nodes.push_back(new Node(arr[i], i));

stack<Node*> stk;
for (int i = 0; i < n; ++i) {
    Node* lastPop = nullptr;
    while (!stk.empty() && stk.top()->val > arr[i]) {
        lastPop = stk.top();
        stk.pop();
    }
    if (!stk.empty())
        stk.top()->right = nodes[i];
    if (lastPop)
        nodes[i]->left = lastPop;
    stk.push(nodes[i]);
}

Node* root = nullptr;
while (!stk.empty()) {
    root = stk.top();
    stk.pop();
}
return root;

登录后复制

}

该方法确保每个节点最多入栈出栈一次，总时间复杂度为O(n)。