OI-wiki 笛卡尔树Cartesian Tree全解定义、单调栈 O(n) 构建与最大子矩形实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki笛卡尔树Cartesian Tree是一种同时满足二叉搜索树与堆性质的二叉树结构是 OI / ICPC 竞赛中连接序列与树形结构的关键桥梁。本文以 OI-wiki 的 笛卡尔树文档 为骨架结合仓库中 参考实现 与 配套测试数据系统讲解笛卡尔树的定义、单调栈线性构建算法以及经典例题 HDU 1506直方图最大子矩形的完整求解过程。读完本文你将掌握笛卡尔树的本质特征、右链维护的单调栈实现并能独立写出 O(n) 建树与子树统计的竞赛代码。引入从键值二元组到树与堆的合体笛卡尔树是一种二叉树每个节点由一个键值二元组 $(k,w)$ 构成并要求键值 $k$ 满足**二叉搜索树BST**的性质中序遍历后 $k$ 有序键值 $w$ 满足堆的性质父节点的 $w$ 小于或大于所有后代节点的 $w$。如果笛卡尔树的 $k,w$ 键值确定且 $k$ 互不相同、$w$ 也互不相同那么这棵笛卡尔树的结构是唯一的。竞赛中最常用的取法是把数组下标当作键值 $k$把数组元素值当作键值 $w$。这样得到的笛卡尔树$k$ 满足 BST 性质$w$ 满足小根堆性质父节点元素值更小。利用二叉搜索树的性质可以推出一个重要结论这种特殊的笛卡尔树满足一棵子树内的下标是一个连续区间——这正是它在许多区间类问题中大显身手的根基。上图所示的笛卡尔树由序列[9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]构建根节点为全局最小值1且任意父节点的值都小于子节点小根堆性质同时树的中序遍历恰好还原出原序列BST 性质。下文统一约定$k$ 满足 BST 性质$w$ 满足堆的性质。单调栈构建笛卡尔树O(n) 线性算法核心过程与右链概念朴素建树每次找区间最小值作为根递归建树复杂度为 $O(n\log n)$ 甚至 $O(n^2)$而 OI-wiki 文档给出的是经典的O(n) 单调栈建树。算法思路是将元素按 $k$ 升序依次插入到当前的笛卡尔树中。为此需要引入一个关键概念定义一棵笛卡尔树的**右链right chain**为从根节点开始一直沿右儿子走下去直到走到一个没有右儿子的节点所形成的链。由于新插入节点的 $k$ 是当前最大的它必然被安插到树的最右端即一定落在右链上同时这个新节点不可能是左儿子也没有右儿子。具体过程如下从右链的下往上逐个比较右链节点与当前节点 $u$ 的 $w$找到第一个满足 $w_x w_u$ 的右链节点 $x$就把 $u$ 接到 $x$ 的右儿子上而 $x$ 原本的右子树整体变成 $u$ 的左子树因为它们的 $k$ 介于 $x$ 与 $u$ 之间且都大于 $w_u$恰好满足 BST 与堆的双重性质。复杂度分析每个数最多进出右链一次每个点在右链中存在的时间是一段连续区间因此用单调栈维护右链即可栈中保存当前笛卡尔树的右链节点一旦某节点不再位于右链就弹出。每个点最多入栈、出栈各一次总复杂度 $O(n)$。C 实现OI-wiki 文档给出的单调栈建树核心代码如下stk维护笛卡尔树节点对应到序列中的下标// stk 维护笛卡尔树中节点对应到序列中的下标 for (int i 1; i n; i) { int k top; // top 表示操作前的栈顶k 表示当前栈顶 while (k 0 w[stk[k]] w[i]) k--; // 维护右链上的节点 if (k) rs[stk[k]] i; // 栈顶元素.右儿子 : 当前元素 if (k top) ls[i] stk[k 1]; // 当前元素.左儿子 : 上一个被弹出的元素 stk[k] i; // 当前元素入栈 top k; }逐行解读这段代码的语义第 2 行k从当前栈顶top开始向左扫描栈内自底向上恰好对应右链自上而下第 3 行只要栈顶元素的w大于当前元素的w不满足小根堆就将其弹出k--这些被弹出的节点将成为 $u$ 的左子树成员第 4 行若k 0说明找到了右链上第一个w更小的节点把 $u$ 挂到它的右儿子上第 5 行若发生了弹出k top则最后被弹出的节点原stk[k1]成为 $u$ 的左儿子第 6-7 行$u$ 入栈并更新栈顶保持栈 新右链的单调性。值得注意的是这里的w比较符号决定建出的是小根堆笛卡尔树若将比较符取反则可得到大根堆笛卡尔树两种形态在竞赛题中各有用途。笛卡尔树与 Treap 的关系OI-wiki 在文档的备注中指出Treap 本质上就是笛卡尔树的一种区别仅在于 Treap 中 $w$即优先级priority的值完全随机。这一关系可以从仓库另一篇文档 Treap树堆 中得到印证Treap 节点同时维护满足 BST 性质的权值val与满足堆性质的随机优先级priority与笛卡尔树的 $(k,w)$ 二元组完全同构。Treap 依赖随机优先级来打乱插入顺序、避免 BST 退化成链而笛卡尔树的 $w$ 则直接取数组元素值。进一步地无旋 Treap 的建树小节 明确给出方法三观察到 treap 是笛卡尔树利用笛卡尔树的 O(n) 建树方法即可用单调栈维护右链即可——这正是本文所讲算法的直接应用场景。也就是说如果 Treap 提前按键值 $k$ 排好序完全可以使用上述单调栈算法在线性时间内完成构建只不过实际竞赛中很少这样用因为排序本身已经带来了 $O(n\log n)$ 的代价。例题实战HDU 1506 直方图最大子矩形问题描述有 $n$ 个位置每个位置的高度为 $h_i$求最大子矩形即直方图中能框出的最大矩形面积。解题思路把下标作为键值 $k$把高度 $h_i$ 作为键值 $w$构建一棵满足小根堆性质的笛卡尔树枚举每个节点 $u$把 $w_u$即高度 $h_u$作为候选矩形的高由于笛卡尔树满足小根堆性质$u$ 的子树内所有节点的高度都 $\ge w_u$因此以 $w_u$ 为高的矩形可以横跨 $u$ 的整个子树又因为子树内下标是一段连续区间矩形的宽就是子树大小于是每个节点贡献的候选面积为w_u × 子树大小取最大值即可一次 DFS 即可算出所有子树大小并更新答案总复杂度 $O(n)$。参考实现与仓库源码OI-wiki 文档中的参考实现对应仓库文件 docs/ds/code/cartesian-tree/cartesian-tree_1.cpp其核心结构如下int cartesian_build(int n) { // 建树满足小根堆性质 for (int i 1; i n; i) { int k i - 1; while (tree[k].val tree[i].val) k tree[k].par; tree[i].ch[0] tree[k].ch[1]; tree[k].ch[1] i; tree[i].par k; tree[tree[i].ch[0]].par i; } return tree[0].ch[1]; } int dfs(int x) { // 一次 dfs 更新答案 if (!x) return 0; int sz dfs(tree[x].ch[0]); sz dfs(tree[x].ch[1]); ans max(ans, (ll)(sz 1) * tree[x].val); return sz 1; }与文档中的数组版ls/rs写法不同这份仓库实现采用了带par父指针与ch[0]/ch[1]左右儿子的节点结构并额外维护了父指针建树同样利用向右链上方寻找第一个w更小的节点通过父指针向上跳跃然后将原节点的右子树整棵挂到新节点左子树完成 O(n) 构建返回根节点编号tree[0].ch[1]哨兵节点0的右儿子求答案dfs后序递归累加子树大小sz每到一个节点用(sz 1) × val更新全局答案ans一次遍历即得结果。仓库中还提供了该参考实现的输入样例与标准答案可直接用于验证程序正确性输入7 2 1 4 5 1 3 3$n7$高度序列2 1 4 5 1 3 3答案为8输入4 1000 1000 1000 1000四个高度均为 1000 的柱子答案为4000输入0表示结束多组数据while (cin n, n)。小结与应用延伸笛卡尔树的核心价值在于把一维序列问题转化为树形结构问题单调栈建树 O(n) 的代价极低可作为预处理步骤子树对应连续区间 子树内 $w$ 满足堆序这两个性质使其天然适配区间最值、最大子矩形、RMQ 类问题从源码结构看OI-wiki 将笛卡尔树文档编排在数据结构目录中与 Treap、二叉搜索树、堆等章节互相引用建议读者结合阅读以建立完整的数据结构知识网络。需要留意的限制是当 $k$ 或 $w$ 存在重复值时笛卡尔树结构不再唯一文档的前提是 $k$、$w$ 均互不相同竞赛中通常通过稳定排序、下标去重或比较符约定来规避这一问题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考