笛卡尔树

一、引入：同时统治“下标”与“数值”的树

给你一个数组 a = [3, 1, 4, 1, 2]，如果我想选出最小值作为整棵树的根，左半边的元素递归建左子树，右半边的元素递归建右子树，最后会搭出一棵怎样的树？

这就是大名鼎鼎的笛卡尔树（Cartesian Tree）。在这棵树里，每个节点带着两份信息：它的“原数组下标”和“数值”。它必须同时满足两个极其严苛的条件：

1. 看下标，是一棵二叉搜索树（BST）：左子树的所有节点下标都比自己小，右子树的所有节点下标都比自己大。中序遍历它，恰好就是原数组的下标顺序 $1, 2, \dots, n$。
2. 看数值，是一个小根堆：父亲节点的值永远不大于孩子节点的值。

边界铁律：如果数组里有重复的数值，比如上面例子里的两个 1（下标 2 和 4），谁来当父亲？为了保证树的唯一性，我们统一规定：值相同时，下标小的优先上位当祖先。你可以理解为，我们真正在比较的是一个二元组 (a[i], i)。

二、暴力建树的痛点：最坏情况的退化

直觉上，我们要建这棵树很简单：在区间里扫一遍找最小值当根，然后把数组切成两半，继续分治。

但仔细想想，如果数组本来就是单调递增的 [1, 2, 3, 4, 5] 呢？ 你每次找最小值都在最左边，右半边越来越短，整棵树退化成了一条向右延伸的超级长链。这会导致每次找最小值的扫描操作直接把总体时间拖成了 $O(N^2)$。更致命的是，递归深度达到了 $N$，如果在考场上用递归写，深链结构会直接把递归调用栈（Call Stack）撑爆。

我们需要一种时间严格为 $O(N)$ 且非递归的“降维打击”建树法。这就要请出我们的老朋友——单调栈。

三、核心构建逻辑：用单调栈维护“最右链”

想象一下，我们从左到右，把数组里的元素一个一个接入树中。 当处理到第 $i$ 个数时，因为它的下标 $i$ 肯定是当前最大的，所以它只能从旧树的最右侧加进去。它绝不可能钻到某个旧节点的左子树内部。

所以，我们只需要用一个栈 st，专门保存这棵树从根节点一路向右走到底的“最右链”。 因为这棵树是一个小根堆，所以这条最右链从上到下（栈底到栈顶），数值一定是单调不降的！

当一个新节点 $i$ 带着数值 a[i] 到来时，会发生什么？

• 它会看向栈顶。如果栈顶的数值比它大，说明栈顶节点“德不配位”，不能继续呆在上方当祖先了，必须弹出退位。
• 循环往复一直弹出，直到栈为空，或者遇到栈顶的值 $\le a[i]$（碰到相等的也不弹，因为旧节点下标小，保留在上位）。
• 此时，最后一个被弹出的节点 last，连同以它为根的整棵子树，一起接到新节点 $i$ 的左侧，last 成为 $i$ 的左儿子。
• 而新节点 $i$，则接力挂到当前栈顶节点（如果栈没空的话）的右儿子位置上。
• 最后，新节点 $i$ 雄赳赳气昂昂地入栈，成为最右链栈顶的新底端。

1. 剥洋葱式手推实战：[3, 1, 4, 1, 2]

（下表中，栈里存的是节点下标，我们时刻关注它的连边操作）

重点来看看第四步的“转接”魔术：

第四步：新节点 4，值为 1。

• 此时栈 st 从底到顶是 [2, 3]（对应数值分别是 1, 4）。
• 我们拿出新数值 1 去和栈顶比。栈顶是节点 3（值 4），比 1 大，弹出！
• 接着看新的栈顶节点 2（值 1）。因为值相等，根据我们的铁律“值相同下标小优先”，节点 2 必须留在上面。停止弹出。
• 此时，最后一个被弹出的节点是 3。我们将节点 3 认作新节点 4 的左儿子；再把新节点 4 接到当前栈顶节点 2 的右儿子位置上。
• 最右链栈更新为 [2, 4]。

第五步：新节点 5，值为 2。栈顶节点 4(值1) < 2，不弹，节点 4 的右儿子设为 5。最终栈变成 [2, 4, 5]。

在这个过程中，每个节点最多进栈一次、出栈一次。哪怕某一步连续退位弹空了整个栈，总体累计的摊还时间复杂度也完美降维到了严格的 $O(N)$。

四、完整程序一：$O(N)$ 笛卡尔树构造模板

场景与协议：给定数组大小 $n$ 和数组元素，构造并输出这棵笛卡尔树的形态。

• 输入：第一行 $n$ ($1 \le n \le 10^6$)，第二行 $n$ 个整数 $|a_i| \le 10^9$。
• 输出：第一行为最终树根的节点编号。接下来 $n$ 行，第 $i$ 行输出节点 $i$ 的左儿子和右儿子编号（空节点用 0 表示）。
• 为了保证后续相关题目大数不溢出，且统一竞赛习惯，本程序开启 #define int long long。（100万节点开 long long 约为 32MB，完全在安全范围内）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;

// a 存数值，lc/rc 存左右儿子编号，st 是灵魂单调栈
int a[N], lc[N], rc[N], st[N];

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    int top = 0;
    for(int i = 1; i <= n; i++){
        int last = 0; // 记录最后一个被弹出的节点
        
        // 核心：栈顶元素如果比新元素大，就要“退位”
        // 注意：遇到相等时必须用 > 判定而不弹，以保障“下标小优先上位”的铁律
        while(top && a[st[top]] > a[i]){
            last = st[top--];
        }
        
        // 如果栈没空，留在栈顶的元素就是新节点的父亲
        if(top) rc[st[top]] = i;
        
        // 最后一个被踢走的节点(连同以它为根的整棵子树)，接为新节点的左儿子
        lc[i] = last;
        
        // 新节点入栈，接管最右链的最底端
        st[++top] = i;
    }
    
    // 最终栈底的第一个元素 st[1] 就是整棵树的全局树根
    cout << st[1] << '\n';
    for(int i = 1; i <= n; i++){
        cout << lc[i] << " " << rc[i] << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

五、物理意义的升华：静态区间最小值 = 树上 LCA

这棵树建出来到底有啥用？它最大的魅力在于，它把数组上的一个一维区间问题，完美转化成了树上的连通拓扑问题。

核心定理：原数组区间 $[L, R]$ 内的最小值，刚好等于笛卡尔树上节点 $L$ 和节点 $R$ 的最近公共祖先 (LCA) 的数值！

为什么？我们一层层剖析：

1. LCA 为什么一定在区间里？ 假设 LCA 的位置下标 $p$ 比 $L$ 还小（$p < L$），那么 $L$ 和 $R$ 都在 $p$ 的右侧，意味着它们应该都在 $p$ 的右子树深处，这就说明 $p$ 根本不是“最近”的祖先（因为右子树里面肯定还有更近的）。同理 $p$ 也不能大于 $R$。所以 $p$ 必定满足 $L \le p \le R$。
2. LCA 为什么一定是最小值？ $p$ 的子树同时包含了节点 $L$ 和节点 $R$，根据中序遍历下标连续的性质，这棵子树必然囊括了整段 $[L, R]$ 区间。既然树结构维持着小根堆特性，子树根节点 $p$ 的值，必定不会大于它任何一个后代节点的值。所以 $a_p$ 就是这段区间里的最小值。

这就是笛卡尔树最迷人的物理意义：当你拿着两个区间端点顺着树往上爬，刚好汇合分叉的那个节点，就是统领这段区间的“最左最小值”所在！

六、完整程序二：基于 LCA 的静态区间最值查询

场景与协议：先建树，再利用倍增 LCA 回答静态区间最小值（RMQ）。

• 输入：第一行 $n, m$，分别表示数组长度和查询次数 ($1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5$)。第二行为数组元素。接下来 $m$ 行每行一个查询闭区间 $L, R$。
• 输出：每行输出该区间的“最小值”和“最左最小值的下标”。
• 算法保障警告：在这份代码预处理倍增 fa 和 dep 数组时，我们特意使用了队列 BFS 迭代遍历。这是因为如果数组原本就是单调递增或全相等的，笛卡尔树就会退化成一条深度为 $n$ 的长链。如果使用图论常规的深搜 DFS 去初始化，直接就会在测评机上触发爆栈 (Stack Overflow)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int LOG=18;

int a[N], lc[N], rc[N], st[N];
// 迭代用的队列，以及树的深度与倍增祖先数组
int q[N], dep[N];
int fa[LOG+1][N];

// 经典倍增求 LCA 模板
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    // 1. 把深的节点往上跳，先把起点深度对齐
    for(int k = LOG; k >= 0; k--){
        if(dep[u] - (1 << k) >= dep[v]){
            u = fa[k][u];
        }
    }
    if(u == v) return u;
    // 2. 两人步调一致往上跳，直到跳到 LCA 的正下方一层
    for(int k = LOG; k >= 0; k--){
        if(fa[k][u] != fa[k][v]){
            u = fa[k][u];
            v = fa[k][v];
        }
    }
    return fa[0][u]; // 再往上走一步就是 LCA
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    // 第 1 步：单调栈 O(N) 建出笛卡尔树
    int top = 0;
    for(int i = 1; i <= n; i++){
        int last = 0;
        while(top && a[st[top]] > a[i]){
            last = st[top--];
        }
        if(top) rc[st[top]] = i;
        lc[i] = last;
        st[++top] = i;
    }
    
    int root = st[1];
    
    // 第 2 步：BFS 迭代遍历树，预处理倍增数组（绝对安全，无惧长链爆栈）
    int head = 0, tail = 0;
    q[tail++] = root;
    dep[root] = 1;
    
    while(head < tail){
        int u = q[head++];
        
        // 计算自己的各级祖先
        for(int k = 1; k <= LOG; k++){
            fa[k][u] = fa[k-1][fa[k-1][u]];
        }
        
        // 儿子进队，把自己的身份塞给儿子的 fa[0]
        if(lc[u]){
            fa[0][lc[u]] = u;
            dep[lc[u]] = dep[u] + 1;
            q[tail++] = lc[u];
        }
        if(rc[u]){
            fa[0][rc[u]] = u;
            dep[rc[u]] = dep[u] + 1;
            q[tail++] = rc[u];
        }
    }
    
    // 第 3 步：O(log N) 在线回答查询
    while(m--){
        int L, R;
        cin >> L >> R;
        int p = lca(L, R); // 找出的 LCA 即为区间最左最小值的下标
        cout << a[p] << " " << p << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

七、物理意义的另一面：子树管辖的连续区间与重复值归属

我们前面提到，笛卡尔树的中序遍历就是原数组的下标顺序。这就引出了一个极其重要的物理意义：笛卡尔树上的每一棵子树，都完美对应着原数组中的一段连续区间。

假设节点 $u$ 管辖的子树包含了原数组中下标从 $L$ 到 $R$ 的元素。因为 $u$ 是这棵小根堆子树的树根，所以 $u$ 一定是这段区间 $[L, R]$ 里的最小值。

那么，这段子树区间是不是等于“仅以 $a_u$ 为限制所能向外扩展的极长物理区间”呢？

这里要特别注意我们前文提到的“边界铁律：值相同时下标小优先”。如果有两个相等的最小值，地盘是怎么划分的？ 比如数组 [2, 1, 3, 1, 4]，有两个 1（下标 2 和 4）。

• 下标 2 的 1 优先上位当整棵树的根，它的子树管辖整个数组 $[1, 5]$，也就是高度 1 能够向外扩展的真正的极长区间。
• 下标 4 的 1 只能屈尊做右子树里的节点，它向左的延伸被老大哥（下标 2 的 1）无情挡住，它管辖的区间被截断为 $[3, 5]$。

这种不对称的管辖权划分意味着：在同一段没有被更小值隔开的区间内，最靠左的同高节点会管辖整个极长区间，而靠右的节点只管辖被切割后的局部区间。 这种严格的分配机制，在解决“计算所有区间最小值之和（贡献法）”类题目时，是一把防止重复统计的绝佳武器。

八、选学：从连续区间到“柱状图最大矩形”

理解了“子树等于连续区间”，我们就打通了笛卡尔树和经典单调栈题目——“柱状图最大矩形”的任督二脉。单调栈的边界扩张方法可以回看《单调栈思想》，这里重点看它与子树区间的联系。

问题场景：给定 $n$ 个非负整数表示柱状图的高度，每个柱子相邻且宽度为 1。求能勾勒出的最大矩形面积。

核心推导： 任何一个最大矩形，必然与某根柱子 $i$ 齐平。以 $a_i$ 为高度向左右延伸的最大宽度，在没有重复高度的情况下，恰好等于以节点 $i$ 为根的子树所管辖的区间长度！

如果有重复高度呢？正如前文推导，在同一段没有被更矮柱子隔开的区间内，靠右的同高节点虽然只能算出一个局部的较小面积，但最靠左的同高节点会把这段里的同高兄弟囊括进自己的子树，算出真正的“最大全景面积”。由于我们只求最大值，右侧节点算出的残缺面积完全不影响最终答案。

更美妙的是，利用单调栈维护最右链的过程，我们甚至不用显式地把树建出来。在节点出入栈的一瞬间，管辖的左右边界就已经确定了：

• 确定左边界：当新柱子 $i$ 入栈踩在此时的栈顶节点 st[top] 身上时，因为遇到等高的柱子也不弹栈，按等值归属规则分给 $i$ 的区间向左延伸到 st[top]+1；栈为空时，左边界就是 1。注意 top 是栈内位置，st[top] 才是柱子的下标。
• 确定右边界：当栈顶 $v$ 被更矮的新柱子 $i$ 弹出时，说明 $v$ 向右碰壁了，最多延伸到 $i - 1$。此时立刻就能结算 $v$ 对应的面积。

1. 剥洋葱式手算：高度数组 [2, 1, 5, 6, 2]

我们重点关注高度为 5（下标 3）和 6（下标 4）的柱子是如何确定边界的：

1. 进栈定左界：节点 3 (高5) 进栈时，前一个留在栈里的是节点 2 (高1)，因此节点 3 的左界是 $2+1=3$。节点 4 (高6) 进栈时踩着节点 3，左界是 $3+1=4$。
2. 出栈定右界：紧接着节点 5 (高2) 到来。因为 2 小于 6，栈顶的节点 4 必须退位出栈，右边界被敲定为 $5-1=4$。结算节点 4 的面积：$6 \times (4 - 4 + 1) = 6$。
3. 继续弹栈：随后节点 3 也被节点 5 弹出，节点 3 的右边界同样敲定为 $5-1=4$。结算节点 3 的面积：$5 \times (4 - 3 + 1) = 10$。

2. 降维解惑：为什么建树和求面积是严格 $O(N)$？

很多同学初学单调栈，看到 for 循环里套着 while，就怕最坏情况退化成 $O(N^2)$。 请回归单调栈维护“最右链”的物理过程： 一个节点诞生时，它进栈 1 次。 当它被更矮的节点挤退位时，它出栈 1 次。一旦降级，它这辈子再也不会回到栈里。 $N$ 个节点，最多 $N$ 次进栈、$N$ 次出栈，操作总次数撑死 $2N$。平摊到每一步就是严格的常数时间 $O(1)$。

3. 完整程序三：借建树逻辑求最大矩形

场景与协议：

• 输入：第一行 $n$ ($1 \le n \le 10^5$)，第二行 $n$ 个整数表示柱子高度 $a_i$ ($0 \le a_i \le 10^9$)。
• 输出：一个整数，表示最大矩形面积。
• 样例输入：
  text复制代码

  5
  2 1 5 6 2
  

• 样例输出：
  text复制代码

  10
  

• 实现要点：为了让残留在栈里的非零高度柱子最终都能顺利弹出结算，在数组末尾人为追加一个高度为 $0$ 的“哨兵”。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int a[N],st[N];
// l[i] 记录第 i 根柱子根据等值归属规则，向左能伸展到的边界下标
int l[N]; 

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	a[n+1]=0; // 哨兵，保证遍历到它时栈内所有非 0 柱子都能被弹出结算
	int top=0,ans=0;
	
	for(int i=1;i<=n+1;i++){
		// 栈顶遇到更矮的柱子，说明向右延伸到头了，弹栈结算
		while(top && a[st[top]]>a[i]){
			int cur=st[top--];
			int r=i-1; // 弹它的柱子前一格，就是它的右边界
			ans=max(ans,a[cur]*(r-l[cur]+1));
		}
		// 新柱子的左边界：等于不弹，所以只能伸展到目前栈顶的右边一格
		l[i]=top?st[top]+1:1;
		st[++top]=i; // 进栈成为新的最右链底端
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

九、总结与实战指引

单纯解决静态 RMQ 问题，使用传统的 ST 表往往更短平快。但我们学习笛卡尔树的重点在于，它能把一个一维数组的区间最值分治结构，具象化成一棵真实的、带有拓扑依赖的二叉树。 在很多涉及“以最值点将区间一分为二”的高级分治 DP 题目中，先用 $O(N)$ 建出这棵树，直接对树进行动态规划，是极其优雅且不可替代的核心思路。

课后训练：模板肌肉记忆

• 洛谷 P5854 【模板】笛卡尔树
  • 训练指引：原题给出长度 $n\le10^7$ 的排列 $p$，要求构建小根堆笛卡尔树。注意内存：存节点编号的大数组 lc、rc、st 可显式使用 int32_t，不必为了这些数组删掉 #define int long long；其他数据按取值范围选类型。提交前仍要核对题目内存限制，估算所有数组的总开销。
  • 输出与避坑：原题输出两项校验和，分别为 $\bigoplus_{i=1}^{n} i\times(l_i+1)$ 和 $\bigoplus_{i=1}^{n} i\times(r_i+1)$，不是本讲第一份程序输出的树形结构。编号数组用了 int32_t，也不代表乘积能用 32 位！计算时加上 1ULL（如 1ULL * i * (lc[i] + 1)），让乘法先在 64 位下进行，两个校验和也用 64 位变量保存。用这题死磕单调栈的那几行灵魂连边操作，反复刻意练习直到形成条件反射。