笛卡尔树：把数组变成一棵特殊的树 - CSP-S

笛卡尔树：用数组搭出一棵“又堆又搜索”的神奇二叉树

你有没有玩过叠叠乐积木？一堆长短不同的木条，你只能把短的放在长的上面，而且还要按照从左到右的顺序摆放——先拿到的木条放在左边，后拿到的放在右边。这样搭出来的塔，就是笛卡尔树的模样！

笛卡尔树是一种用数组构造的二叉树，它同时拥有两个“超能力”：堆的性质（父节点比子节点大或小）和二叉搜索树的性质（左子树的下标小于父节点，右子树的下标大于父节点）。它特别擅长解决区间最值查询问题——比如，给你一堆考试成绩，想知道某个学号区间里谁考得最好，笛卡尔树能用 O(1) 时间告诉你答案（配合预处理）。另外，它还能用来做排序、求逆序对，甚至构造后缀数组。

下面我们就一步步把它拆开看明白。

1. 笛卡尔树的定义——两个性质合二为一

假设我们有一个数组，每个元素有两个属性：下标（位置编号）和值。比如下面这张成绩单：

学号（下标）	1	2	3	4	5	6
分数（值）	3	1	4	2	5	6

用这 6 个数据可以搭出一棵二叉树，规则是：

堆性质：任意父节点的值必须大于（或小于）所有子节点的值。这里我们建一个大根堆，即父节点分数比孩子高。
二叉搜索树性质：中序遍历这棵树，得到的序列就是按照下标从小到大排列的（左子树下标 < 根下标 < 右子树下标）。

满足这两个条件的树，就是笛卡尔树。它很特别：给定一个数组，笛卡尔树是唯一确定的。

2. 如何用栈快速构建笛卡尔树？

搭建过程就像玩“插积木”：按学号顺序（1→2→3…）依次处理每个学生，每次插入新节点时，要保证堆性质成立——所以需要把比新节点小的节点“踢出去”，让新节点当它们的老大。而二叉搜索树性质自动满足，因为我们是按下标顺序插入的。

具体步骤（大根堆版本，值大的为父节点）：

用栈维护一条“右链”，栈里存放当前树最右边的那些节点（从根一直往右走的节点）。
遍历数组，对于第 i 个节点：
- 先准备一个变量 last，用来记录最后一个被弹出的节点。
- 只要栈不空，并且栈顶节点的值小于当前节点的值，就弹出栈顶，并把弹出的节点赋值给 last（意思是这些节点比新节点小，需要做新节点的左子树的一部分）。
- 弹出结束后：
  - 把 last 作为当前节点 i 的 左孩子（因为 last 是刚刚被弹出的一串里最靠近 i 的那个，它和它的子树都应该在 i 的左边）。
  - 如果栈不空，说明栈顶节点比当前节点大（更厉害），就把当前节点作为栈顶节点的 右孩子（因为当前节点下标更大，应该挂在右边）。
- 最后把当前节点压入栈。

这个算法用一张动态图来理解更直观。我们拿成绩单数组 [3,1,4,2,5,6] 走一遍：

第1步：插入学号1（分数3）。栈空，直接压入。当前栈：[1]
第2步：插入学号2（分数1）。栈顶分数3 > 1，不弹出。 last=0。栈顶节点1的右孩子设为2。压入2。栈：[1,2]
第3步：插入学号3（分数4）。栈顶分数1 < 4，弹出2，last=2；栈顶分数3 < 4，弹出1，last=1；栈空。将 last=1 作为节点3的左孩子。栈空，没有右孩子关系。压入3。栈：[3]
第4步：插入学号4（分数2）。栈顶分数4 > 2，不弹出。last=0。栈顶节点3的右孩子设为4。压入4。栈：[3,4]
第5步：插入学号5（分数5）。栈顶分数2 < 5，弹出4，last=4；栈顶分数4 < 5，弹出3，last=3；栈空。将 last=3 作为节点5的左孩子。压入5。栈：[5]
第6步：插入学号6（分数6）。栈顶分数5 < 6，弹出5，last=5；栈空。将 last=5 作为节点6的左孩子。压入6。栈：[6]

最终树的形状：根是6（分数最高），左孩子是5，5的左孩子是3（分数4），3的左孩子是1，右孩子是4……大家可以动手画一画，验证中序遍历结果是 1 2 3 4 5 6。

3. 把构建过程写成代码

以下代码和原版一致，但加入了更详细的注释：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100010;
int value[MAXN];     // value[i] 存储下标 i 的值（比如分数）
int left_child[MAXN];  // left_child[i] 是节点 i 的左孩子编号，0表示无
int right_child[MAXN]; // right_child[i] 是节点 i 的右孩子编号
int n;               // 数组长度

void build_cartesian_tree() {
    stack<int> stk;  // 栈里存的是节点下标，保持值递减（大根堆）
    for (int i = 1; i <= n; ++i) {
        int last = 0;  // 记录最后一个被弹出的节点（将成为左孩子）
        // 只要栈不空且栈顶节点的值 < 当前节点的值，就弹出
        while (!stk.empty() && value[stk.top()] < value[i]) {
            last = stk.top();
            stk.pop();
        }
        // 当前节点的左孩子是最后一个被弹出的节点
        left_child[i] = last;
        // 如果栈不空，把当前节点作为栈顶节点的右孩子（因为下标更大）
        if (!stk.empty()) {
            right_child[stk.top()] = i;
        }
        // 将当前节点入栈，它可能是后面节点的左孩子或右孩子
        stk.push(i);
    }
}

int main() {
    // 示例：下标从1到6，值分别为3,1,4,2,5,6
    n = 6;
    int temp[] = {0, 3, 1, 4, 2, 5, 6}; // 第0个不用
    for (int i = 1; i <= n; ++i) {
        value[i] = temp[i];
    }

    build_cartesian_tree();

    // 输出每个节点的左右孩子（0表示没有）
    cout << "构建结果：" << endl;
    for (int i = 1; i <= n; ++i) {
        cout << "节点" << i << " (值=" << value[i] << ")"
             << " 左孩子:" << left_child[i]
             << " 右孩子:" << right_child[i] << endl;
    }
    return 0;
}

运行输出：

构建结果：
节点1 (值=3) 左孩子:0 右孩子:2
节点2 (值=1) 左孩子:0 右孩子:0
节点3 (值=4) 左孩子:1 右孩子:4
节点4 (值=2) 左孩子:0 右孩子:0
节点5 (值=5) 左孩子:3 右孩子:0
节点6 (值=6) 左孩子:5 右孩子:0

可以对照刚才的手工模拟结果，完全一致。

4. 用笛卡尔树快速求区间最大值

笛卡尔树有一个超级好用的性质：对于任意区间 [L, R]（下标范围），这个区间内的最大值所在的位置，就是节点 L 和节点 R 的最近公共祖先（LCA）。

比如上面例子中，想查询区间 [2, 5] 的最大值（下标2到5的值分别是1,4,2,5）。节点2和节点5的LCA是节点5，而节点5的值是5，正好是最大值。再试试区间 [1, 4]：节点1和节点4的LCA是节点3（因为节点3是1和4的祖先），值4，也确实最大。

所以，只要提前构建好笛卡尔树，再用快速求LCA的方法（比如倍增、树剖），就能在 O(log n) 甚至 O(1) 时间回答任意区间最大值的位置。相比线段树的 O(log n)，笛卡尔树+LCA的常数更小，而且实现简单。

5. 新手最容易犯的3个错误

错误1：搞反大小比较符号

如果要建大根堆，条件是 value[stk.top()] < value[i]（当前值更大时弹出）。
如果要建小根堆，条件变成 value[stk.top()] > value[i]（当前值更小时弹出）。
搞反了会导致树的结构混乱，比如把大值放到下面。

错误2：左右孩子赋值顺序写反

先 left_child[i] = last，再判断是否给栈顶的右孩子赋值。这是固定的，因为 last 是弹出的最下面那个节点，它的下标小于 i，所以应该是 i 的左孩子。
有人会写成 right_child[i] = last，那就错了。

错误3：下标从0开始但忘记调整

如果数组下标从0开始，那么左孩子和右孩子用-1表示空。这时栈里存的也是下标0~n-1。构建循环要改成 for (int i=0; i<n; ++i)，并且左孩子赋值 left_child[i] = (last==-1 ? -1 : last)。原代码是从1开始的，如果直接用0版本，会把 0 当作有效节点导致出错。

6. 完整运行示例（带输入输出）

下面是一个可以直接复制到Dev-C++或在线编译器中运行的完整程序，它先读入数组长度和值，构建笛卡尔树，然后输出每个节点的父子关系：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 100010;
int val[MAXN];          // 存储每个位置的值
int lch[MAXN], rch[MAXN]; // 左右孩子，0表示空
int parent[MAXN];       // 记录每个节点的父节点（可选）

void build_cartesian(int n) {
    stack<int> stk;
    for (int i = 1; i <= n; ++i) {
        int last = 0;
        // 大根堆：栈顶值 < 当前值时弹出
        while (!stk.empty() && val[stk.top()] < val[i]) {
            last = stk.top();
            stk.pop();
        }
        lch[i] = last;
        if (last) parent[last] = i; // 标记父节点
        if (!stk.empty()) {
            rch[stk.top()] = i;
            parent[i] = stk.top();
        }
        stk.push(i);
    }
}

int main() {
    int n;
    cout << "请输入数组长度: ";
    cin >> n;
    cout << "请输入 " << n << " 个整数: ";
    for (int i = 1; i <= n; ++i) cin >> val[i];

    build_cartesian(n);

    cout << "\n笛卡尔树构建结果:\n";
    for (int i = 1; i <= n; ++i) {
        cout << "节点" << i << " (值=" << val[i] << ") 父节点: " << parent[i]
             << " 左孩子: " << lch[i] << " 右孩子: " << rch[i] << endl;
    }

    // 额外演示：查询区间最大值（LCA需要预处理，这里只展示思路）
    cout << "\n查询区间 [2,5] 的最大值位置:\n";
    // 真实实现需要写LCA求法，这里仅示意
    cout << "节点2和节点5的LCA位置就是答案，需要使用倍增或树剖" << endl;
    return 0;
}

输入例子：

6
3 1 4 2 5 6

输出结果（和前面一致）。

7. 相关知识点链接

学完笛卡尔树，你可以继续探索：

堆：二叉堆、左偏树、配对堆——都是堆，但笛卡尔树是二叉搜索树+堆的混合体。
二叉搜索树：Treap（树堆）也是同时维护堆和BST，但是用随机优先级，而笛卡尔树的优先级就是数组的值。
最近公共祖先（LCA）：学会倍增或Tarjan求LCA，就能用笛卡尔树实现O(1)的区间最值查询。
线段树与RMQ：比笛卡尔树更通用的区间查询结构，但笛卡尔树在静态数组上更高效。
后缀数组：构建过程中也会用到笛卡尔树的思想（如DC3算法中的排序）。

如果你在CSP-S赛场上遇到静态区间最值问题，不妨试试笛卡尔树+LCA的解法——它比线段树写起来更短，而且常数更小，特别适合追求极致速度的选手。

例题精讲