用单调栈建笛卡尔树必须满足：①下标天然递增（保证中序为原数组顺序）；②值域满足堆序（小根堆则栈递增，大根堆则递减），且重复值需加下标平局规则。
用单调栈建笛卡尔树必须满足的两个前提
不是所有数组都能直接套模板建出合法笛卡尔树。必须同时满足：
– 下标（或键）天然递增：你按 i = 0,1,2,...,n-1 顺序遍历数组，隐含了 BST 的中序遍历顺序；
– 值域用于堆序：通常建小根堆（即父节点 val ≤ 子节点 val），此时单调栈需维护「值递增」的右链（栈底→栈顶值递增）；若建大根堆，则栈需递减。
违反任一前提，比如打乱下标顺序、或对重复值不加平局规则，会导致中序无法还原原数组，或堆序断裂。
单调栈建树的核心循环逻辑
关键不是“压栈”，而是「弹栈找父、挂左子、接右子」三步原子操作。常见错误是只处理了父子关系的一侧，或漏掉指针更新：
- 每次取
arr[i]，从栈顶开始弹出所有val > arr[i]的节点（小根堆下）——这些节点将构成新节点的左子树链 - 弹完后，若栈非空，当前节点成为栈顶节点的
right子节点；否则它是新根 - 被弹出的最后一个节点（即第一个比
arr[i]大的），成为当前节点的left子节点 - 最后把当前节点入栈——它现在是右链新末端
注意：left 和 right 是反直觉的：新节点的 left 指向「刚被踢出右链的较大值节点」，不是它左边的邻居。
vector 存储比指针更稳，且更快
用 new Node 动态分配节点，指针跳转破坏 CPU 缓存局部性，大数据量 RMQ 查询时性能掉 2–3 倍。推荐用三个平行 vector<int></int>：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
vector<int> left(n, -1), right(n, -1), parent(n, -1)</int>- 栈里存的是下标
i，不是指针，所有访问都是连续内存 - 构建完后，
left[i]/right[i]直接给出子节点下标，无需解引用 - 重复值处理：当
arr[i] == arr[stk.top()]时，加判据i 或 <code>i > stk.top()打破平局，保证构造唯一
容易忽略的边界与调试陷阱
这几个点不加防护，程序可能静默错、段错误或 RMQ 返回错误下标：
- 栈为空时，别对
stk.top()解引用——循环前先if (stk.empty())分支处理 -
pos数组（记录每个下标在欧拉序中首次出现位置）必须初始化为-1，否则未访问节点参与min计算会污染结果 - ST 表预处理用的
log2必须是整数向下取整（如int lg = 31 - __builtin_clz(len)），std::log2浮点误差可能导致st[i][j]越界 - 建树后做一次中序遍历，检查输出下标是否为
0,1,2,...,n-1——这是验证 BST 性质最廉价的手段
真正难的不是写对建树循环，而是让同一数组多次运行得到相同树结构，且后续 RMQ 不因缓存/浮点/初始化问题漂移——这些细节才决定它能不能进生产代码。
