笛卡尔树通过结合二叉搜索树和堆性质，将RMQ问题转化为LCA问题，利用单调栈在O(n)时间内构建，并配合DFS与稀疏表实现O(1)查询，适用于静态数据的高效区间最值查询。
笛卡尔树（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;}
用于自动切换项目中适合的node 版本
下载
根据 package.json 中的 engines 字段自动检测 Node.js 版本需求，未安装 nvm 时自动安装并切换至对应版本。支持 Windows、macOS、Linux。适用于 Node.js 项目开发、版本切换和环境配置。
该方法确保每个节点最多入栈出栈一次，总时间复杂度为O(n)。
结合RMQ的高效查询方案
构建笛卡尔树后，RMQ(a, b)等价于查找节点a和b在树中的LCA。可通过以下步骤实现高效查询：
- 对笛卡尔树进行DFS，记录访问节点序列、深度序列和首次出现位置。
- 将LCA问题转化为新的RMQ问题（在深度序列上找最小值）。
- 使用稀疏表（Sparse Table）预处理深度序列，实现O(1)查询。
整体流程：原数组 → 构建笛卡尔树 → DFS生成Euler Tour → ST表预处理 → O(1) RMQ查询。
实际应用场景与注意事项
笛卡尔树适用于静态或半静态数据的RMQ场景，如：
- 滑动窗口最小值
- 直方图最大矩形面积
- 字符串算法中的某些优化
注意点：
- 若数组有重复元素，需定义索引优先规则以保证堆性质唯一性。
- 动态更新代价较高，不适合频繁修改的场景。
- 指针操作易出错，可改用数组下标模拟树结构提升稳定性。
基本上就这些，掌握构建和转化思想后，配合ST表就能高效解决多数RMQ问题。
