本课时有配套视频讲解，购买后即可观看（永久有效）
笛卡尔树
一、课上练习
编程练习
- 笛卡尔树：L49969
二、知识总结
✨ 核心思想
笛卡尔树（Cartesian Tree）是一种同时满足二叉搜索树（BST）和堆性质的二叉树：
- BST 性质：按下标（位置）排列，中序遍历结果就是原数组
- 堆性质：按值排列，父节点的值不大于子节点的值（小根堆笛卡尔树）
笛卡尔树将位置信息和值信息巧妙地统一在一棵树中，在 RMQ、区间最值分治等问题中有重要应用。
✨ 算法原理
笛卡尔树的定义
给定数组 a[1..n]，其笛卡尔树递归定义如下：
- 找到数组中的最小值
a[k]，k作为根节点 a[1..k-1]递归构建左子树a[k+1..n]递归构建右子树
O(n) 构建算法
利用单调栈可以在 O(n) 时间内构建笛卡尔树：
- 从左到右依次插入元素
- 维护一个从根到最右链的单调递增栈
- 插入新元素
a[i]时：- 弹出栈中所有值大于
a[i]的节点 - 最后弹出的节点成为
i的左子 i成为栈顶节点的右子- 将
i入栈
- 弹出栈中所有值大于
与 Treap 的关系
Treap = Tree + Heap。Treap 的每个节点有两个属性：key（满足 BST 性质）和 priority（满足堆性质）。如果 priority 是随机值，则构成随机化 BST；如果 priority 是确定的值，则本质上就是笛卡尔树。
✨ 代码实现
笛卡尔树 O(n) 构建
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 10000005;
5
6int a[MAXN];
7int ls[MAXN], rs[MAXN]; // 左右子节点
8int stk[MAXN]; // 单调栈
9int n;
10
11// O(n)构建笛卡尔树，返回根节点编号
12int buildCartesianTree() {
13 int top = 0; // 栈顶指针
14
15 for (int i = 1; i <= n; i++) {
16 ls[i] = rs[i] = 0;
17 int last = 0; // 记录最后弹出的节点
18
19 // 弹出所有值大于a[i]的节点
20 while (top > 0 && a[stk[top]] > a[i]) {
21 last = stk[top];
22 top--;
23 }
24
25 // 最后弹出的节点成为i的左子
26 if (last) ls[i] = last;
27
28 // i成为栈顶节点的右子
29 if (top > 0) rs[stk[top]] = i;
30
31 // i入栈
32 stk[++top] = i;
33 }
34
35 return stk[1]; // 栈底就是根节点
36}
37
38int main() {
39 ios::sync_with_stdio(false);
40 cin.tie(nullptr);
41
42 cin >> n;
43 for (int i = 1; i <= n; i++) cin >> a[i];
44
45 int root = buildCartesianTree();
46
47 // 验证：用异或和检验左右子节点
48 long long lxor = 0, rxor = 0;
49 for (int i = 1; i <= n; i++) {
50 lxor ^= (long long)i * (ls[i] + 1);
51 rxor ^= (long long)i * (rs[i] + 1);
52 }
53 cout << lxor << " " << rxor << "\n";
54
55 return 0;
56}笛卡尔树上的 DFS 应用
笛卡尔树求最大矩形面积（直方图问题）
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5typedef long long ll;
6
7int a[MAXN]; // 直方图高度
8int ls[MAXN], rs[MAXN];
9int sz[MAXN]; // 子树大小（即区间长度）
10int stk[MAXN];
11int n;
12
13int buildCartesianTree() {
14 int top = 0;
15 for (int i = 1; i <= n; i++) {
16 ls[i] = rs[i] = 0;
17 int last = 0;
18 while (top > 0 && a[stk[top]] > a[i]) {
19 last = stk[top--];
20 }
21 if (last) ls[i] = last;
22 if (top > 0) rs[stk[top]] = i;
23 stk[++top] = i;
24 }
25 return stk[1];
26}
27
28// 计算子树大小
29int calcSize(int u) {
30 if (u == 0) return 0;
31 sz[u] = 1 + calcSize(ls[u]) + calcSize(rs[u]);
32 return sz[u];
33}
34
35// 在笛卡尔树上DFS求最大矩形面积
36ll ans = 0;
37
38void dfs(int u) {
39 if (u == 0) return;
40 // 以a[u]为高度，宽度为子树大小（即该区间长度）
41 ans = max(ans, (ll)a[u] * sz[u]);
42 dfs(ls[u]);
43 dfs(rs[u]);
44}
45
46int main() {
47 ios::sync_with_stdio(false);
48 cin.tie(nullptr);
49
50 cin >> n;
51 for (int i = 1; i <= n; i++) cin >> a[i];
52
53 int root = buildCartesianTree();
54 calcSize(root);
55 dfs(root);
56
57 cout << ans << "\n";
58
59 return 0;
60}✨ 执行示例
以数组 a = [3, 2, 6, 1, 9]（下标 1~5）构建小根堆笛卡尔树。
单调栈模拟过程：
| 步骤 | 插入 | 栈（底→顶） | 操作 |
|---|---|---|---|
| 1 | a[1]=3 | [1] | 直接入栈 |
| 2 | a[2]=2 | [2] | 弹出1（3>2），1成为2的左子，2入栈 |
| 3 | a[3]=6 | [2, 3] | 6>2，直接入栈，3成为2的右子 |
| 4 | a[4]=1 | [4] | 弹出3（6>1），弹出2（2>1），2成为4的左子，4入栈 |
| 5 | a[5]=9 | [4, 5] | 9>1，直接入栈，5成为4的右子 |
最终笛卡尔树：
4(a=1)
/ \
2(a=2) 5(a=9)
/ \
1(a=3) 3(a=6)验证：
- 中序遍历：1 → 2 → 3 → 4 → 5（按下标递增，满足 BST）
- 父节点值 ≤ 子节点值（满足小根堆）
✨ 解题步骤详解
笛卡尔树的典型应用
1. 直方图最大矩形面积
经典问题：给定直方图的高度数组，求最大矩形面积。
建笛卡尔树后，每个节点 u 代表一个区间，a[u] 是区间最小值，子树大小是区间长度。最大矩形面积 = max(a[u] * sz[u])。
2. RMQ 问题
笛卡尔树天然编码了 RMQ 信息：区间 [l, r] 的最小值就是 l 和 r 在笛卡尔树上 LCA 的值。结合 Euler Tour + ST 表可实现 O(1) RMQ。
3. 区间分治
很多分治问题（如合并排序树等）的分治点恰好是区间最值，此时笛卡尔树提供了自然的分治结构。
构建的关键理解
单调栈维护的是从根到最右链的路径。每次插入新元素时，弹出的节点"断开"成为新节点的左子树，新节点接入最右链。
✨ 常见错误
- 大根堆和小根堆搞混：根据题意选择。求最大矩形通常用小根堆笛卡尔树。
- 栈为空时访问 stk[top]：插入时要先检查
top > 0。 - 左右子节点赋值顺序错误：弹出的节点成为新节点的左子，不是右子。
- 递归 DFS 栈溢出：n 很大时笛卡尔树可能退化为链（如单调递增数组），此时递归深度为 n，需要改为迭代或手动栈。
- 忘记初始化 ls 和 rs：构建前必须将所有节点的子节点清零。
✨ 算法评价
| 指标 | 复杂度 |
|---|---|
| 构建时间 | O(n) |
| 空间复杂度 | O(n) |
优点：
- O(n) 线性构建，非常高效
- 将位置和值的信息统一编码在树结构中
- 为 RMQ 和分治提供天然的结构
缺点：
- 不支持动态插入删除（静态结构）
- 可能退化为链，递归时需注意
与单调栈的关系：笛卡尔树的构建过程本质就是单调栈。很多单调栈能解决的问题，换用笛卡尔树的视角可以更直观地理解。