一、算法背景与核心思想
笛卡尔树（Cartesian Tree）是一种同时满足堆性质与二叉搜索树性质的特殊数据结构。对于给定序列，笛卡尔树以序列最小值（或最大值）为根，左子树递归构建于最小值左侧子序列，右子树递归构建于最小值右侧子序列。这使得它天然适合解决区间最值查询（RMQ）问题。
与传统线段树 O(n) 建树、O(log n) 查询相比，笛卡尔树可以在 O(n) 时间内完成构建，并配合 O(1) 的LCA（最近公共祖先）查询，实现 RMQ 的常数级响应。本文将详细讲解其线性构建算法，并提供可直接运行的完整 Java 实现。
二、笛卡尔树的定义与性质
给定一个序列 A[0..n-1]，其笛卡尔树满足以下两条核心性质：
- 堆性质（Heap Property）：每个节点的值不大于（或不小于）其子节点的值。以最小值堆为例，根节点为全局最小值。
- 中序遍历有序（BST Property）：对笛卡尔树进行中序遍历，得到的序列恰好是原序列
A[0..n-1]。
以序列 [3, 1, 4, 1, 5, 9, 2, 6] 为例，其最小堆笛卡尔树结构如下：
- 根节点为全局最小值
1（索引1处的值） - 左子树由
[3]构建，右子树由[4, 1, 5, 9, 2, 6]构建 - 右子树的根为右半部分最小值
1（索引3处的值） - 依此类推递归构建
三、基于单调栈的线性构建算法
3.1 算法思路
若采用递归分治构建，时间复杂度为 O(n log n)。而利用单调栈，我们可以在 O(n) 时间内完成构建。
核心观察：按序列从左到右依次插入节点时，新节点 A[i] 会沿着当前树的最右链向上”爬升”，直到找到值比它小（最小堆）的节点作为父节点。这一”最右链爬升”过程恰好可以用单调栈维护：
- 维护一个值递增的单调栈
- 每来一个新节点，弹出栈顶所有比它大的节点
- 最后被弹出的节点成为新节点的左孩子
- 新节点成为当前栈顶节点的右孩子
3.2 算法步骤详解
初始化空栈
for i = 0 to n-1:
last = null
while 栈非空 且 栈顶节点值 > A[i]:
last = 栈顶弹出
if 栈非空:
栈顶节点的右孩子 = i
if last != null:
i的左孩子 = last
将i压入栈
栈底元素即为根节点
四、RMQ问题的笛卡尔树解法
4.1 核心定理
对于序列 A 构建的最小堆笛卡尔树，查询区间 [l, r] 的最小值，等价于求原序列中 l 位置和 r 位置对应节点在笛卡尔树上的最近公共祖先（LCA）。该LCA节点对应的值，即为区间 [l, r] 的最小值。
4.2 LCA预处理
为支持 O(1) RMQ 查询，需要对笛卡尔树进行LCA预处理：
- 欧拉遍历：DFS遍历树，记录访问的节点序列和对应深度
- 首次出现数组：记录每个节点在欧拉序列中首次出现的位置
- RMQ（Sparse Table）：在欧拉序列的深度数组上构建ST表，实现O(1)的LCA查询
由于欧拉序列长度为 2n-1，ST表构建复杂度为 O(n log n)，查询为 O(1)。
五、完整Java实现
import java.util.*;
/**
* 笛卡尔树实现：线性构建 + RMQ查询
* 基于单调栈的O(n)建树算法，配合欧拉序+ST表实现O(1)区间最值查询
*/
public class CartesianTree {
// ========== 笛卡尔树节点定义 ==========
static class Node {
int val; // 节点值
int index; // 在原序列中的索引
int left; // 左孩子索引，-1表示空
int right; // 右孩子索引，-1表示空
int parent; // 父节点索引，-1表示根
Node(int val, int index) {
this.val = val;
this.index = index;
this.left = -1;
this.right = -1;
this.parent = -1;
}
}
private final int n; // 序列长度
private final int[] arr; // 原序列
private final Node[] nodes; // 笛卡尔树节点数组
private int root; // 根节点索引
// ========== LCA预处理相关数组 ==========
private int[] euler; // 欧拉遍历序列（节点索引）
private int[] depthEuler; // 欧拉序列对应深度
private int[] firstOccur; // 每个节点在欧拉序列中首次出现的位置
private int eulerSize; // 欧拉序列长度
private int[][] st; // Sparse Table
private int[] logTable; // 预计算的对数表
/**
* 构造函数：构建笛卡尔树
* @param arr 输入序列
*/
public CartesianTree(int[] arr) {
this.n = arr.length;
this.arr = arr.clone();
this.nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(arr[i], i);
}
buildCartesianTree();
preprocessLCA();
}
/**
* 基于单调栈的O(n)笛卡尔树构建算法
* 维护值递增的栈，确保最小堆性质
*/
private void buildCartesianTree() {
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int last = -1;
// 弹出所有值大于当前节点的栈顶元素
while (!stack.isEmpty() && nodes[stack.peek()].val > nodes[i].val) {
last = stack.pop();
}
// 当前栈顶成为当前节点的父节点（右孩子关系）
if (!stack.isEmpty()) {
nodes[i].parent = stack.peek();
nodes[stack.peek()].right = i;
}
// 最后被弹出的节点成为当前节点的左孩子
if (last != -1) {
nodes[last].parent = i;
nodes[i].left = last;
}
stack.push(i);
}
// 栈底元素为根节点（单调栈中最后剩下的最小值）
while (stack.size() > 1) {
stack.pop();
}
root = stack.isEmpty() ? -1 : stack.peek();
}
/**
* LCA预处理：欧拉遍历 + Sparse Table
*/
private void preprocessLCA() {
euler = new int[2 * n];
depthEuler = new int[2 * n];
firstOccur = new int[n];
Arrays.fill(firstOccur, -1);
eulerSize = 0;
dfs(root, 0);
// 构建对数表
logTable = new int[eulerSize + 1];
logTable[1] = 0;
for (int i = 2; i <= eulerSize; i++) {
logTable[i] = logTable[i / 2] + 1;
}
// 构建Sparse Table
int k = logTable[eulerSize] + 1;
st = new int[eulerSize][k];
for (int i = 0; i < eulerSize; i++) {
st[i][0] = i; // 初始时每个位置的最小值就是自身
}
for (int j = 1; j < k; j++) {
for (int i = 0; i + (1 << j) <= eulerSize; i++) {
int left = st[i][j - 1];
int right = st[i + (1 << (j - 1))][j - 1];
st[i][j] = depthEuler[left] < depthEuler[right] ? left : right;
}
}
}
/**
* DFS生成欧拉遍历序列
* @param u 当前节点索引
* @param depth 当前深度
*/
private void dfs(int u, int depth) {
if (u == -1) return;
// 记录首次出现位置
if (firstOccur[u] == -1) {
firstOccur[u] = eulerSize;
}
euler[eulerSize] = u;
depthEuler[eulerSize] = depth;
eulerSize++;
if (nodes[u].left != -1) {
dfs(nodes[u].left, depth + 1);
euler[eulerSize] = u;
depthEuler[eulerSize] = depth;
eulerSize++;
}
if (nodes[u].right != -1) {
dfs(nodes[u].right, depth + 1);
euler[eulerSize] = u;
depthEuler[eulerSize] = depth;
eulerSize++;
}
}
/**
* 查询区间[l, r]的最小值（基于LCA的O(1)查询）
* @param l 左边界（包含）
* @param r 右边界（包含）
* @return 区间最小值
*/
public int queryMin(int l, int r) {
if (l > r) {
int tmp = l;
l = r;
r = tmp;
}
int fl = firstOccur[l];
int fr = firstOccur[r];
if (fl > fr) {
int tmp = fl;
fl = fr;
fr = tmp;
}
int j = logTable[fr - fl + 1];
int left = st[fl][j];
int right = st[fr - (1 << j) + 1][j];
int lcaIndex = depthEuler[left] < depthEuler[right] ? left : right;
return arr[euler[lcaIndex]];
}
/**
* 获取笛卡尔树的根节点索引
*/
public int getRoot() {
return root;
}
/**
* 打印树的结构（用于调试）
*/
public void printTree() {
System.out.println("笛卡尔树结构（根节点索引: " + root + ", 值: " + (root >= 0 ? nodes[root].val : "null") + ")");
for (int i = 0; i < n; i++) {
System.out.printf(" 节点[%d] val=%d, left=%d, right=%d, parent=%d%n",
i, nodes[i].val, nodes[i].left, nodes[i].right, nodes[i].parent);
}
}
// ========== 主程序：测试与演示 ==========
public static void main(String[] args) {
// 测试序列
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
System.out.println("原序列: " + Arrays.toString(arr));
System.out.println();
CartesianTree ct = new CartesianTree(arr);
ct.printTree();
System.out.println();
// RMQ查询测试
int[][] queries = {
{0, 7}, {0, 2}, {2, 5}, {4, 7}, {1, 3}, {5, 5}
};
System.out.println("RMQ查询结果:");
for (int[] q : queries) {
int l = q[0], r = q[1];
int min = ct.queryMin(l, r);
System.out.printf(" 区间[%d, %d] 最小值 = %d%n", l, r, min);
}
// 验证正确性：暴力对比
System.out.println("\n暴力验证:");
for (int[] q : queries) {
int l = q[0], r = q[1];
int brute = arr[l];
for (int i = l + 1; i <= r; i++) {
brute = Math.min(brute, arr[i]);
}
int tree = ct.queryMin(l, r);
System.out.printf(" [%d, %d] 暴力=%d, 笛卡尔树=%d, %s%n",
l, r, brute, tree, brute == tree ? "正确" : "错误!");
}
// 大规模性能测试
System.out.println("\n大规模性能测试 (n=100000, 100000次查询):");
int n = 100000;
int[] largeArr = new int[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) {
largeArr[i] = rand.nextInt(1000000);
}
long startBuild = System.currentTimeMillis();
CartesianTree largeCt = new CartesianTree(largeArr);
long buildTime = System.currentTimeMillis() - startBuild;
System.out.println(" 建树时间: " + buildTime + " ms");
int qCount = 100000;
long startQuery = System.currentTimeMillis();
for (int i = 0; i < qCount; i++) {
int l = rand.nextInt(n);
int r = rand.nextInt(n);
if (l > r) {
int tmp = l;
l = r;
r = tmp;
}
largeCt.queryMin(l, r);
}
long queryTime = System.currentTimeMillis() - startQuery;
System.out.println(" " + qCount + "次查询时间: " + queryTime + " ms");
System.out.println(" 平均单次查询: " + (queryTime * 1000000.0 / qCount) + " ns");
}
}
六、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 建树 | O(n) | O(n) | 单调栈保证每个节点最多入栈出栈各一次 |
| LCA预处理 | O(n log n) | O(n log n) | 欧拉序列长度 2n-1，ST表空间 |
| 单次RMQ查询 | O(1) | O(1) | ST表上的区间最值查询 |
若只需建树而不需要频繁查询，可以省略LCA预处理。若查询次数 Q 远大于 n，则笛卡尔树 + LCA 的 O(n log n + Q) 总复杂度显著优于线段树的 O(n + Q log n)。
七、算法扩展与应用场景
- 最大堆笛卡尔树：将单调栈中的比较符号反转即可构建以最大值为根的笛卡尔树。
- 子数组最值贡献：利用笛卡尔树可以高效统计每个元素作为区间最值的子数组个数，常用于组合计数问题。
- 单调栈的等价视角：笛卡尔树的构建过程本质上就是单调栈维护”最右链”的过程，理解笛卡尔树有助于深化对单调栈本质的认识。
- 与Treap的对比：笛卡尔树是确定的（由序列唯一确定），而Treap引入随机优先级以保证期望平衡，两者都利用了堆+BST的双重性质。
八、总结
笛卡尔树通过巧妙地融合堆性质与二叉搜索树性质，将序列的区间最值查询转化为树上的LCA问题。基于单调栈的线性构建算法是其核心亮点——每个节点仅入栈出栈一次，实现了理论最优的 O(n) 建树效率。配合欧拉遍历与Sparse Table的LCA预处理，RMQ查询可以降至常数时间。掌握笛卡尔树，不仅能高效解决区间最值问题，更能加深对单调栈、树形结构和LCA之间内在联系的理解。
