笛卡尔树复习笔记

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了笛卡尔树复习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含924字，纯文字阅读大概需要2分钟。

内容图文

只考虑排列，因为模板题也只是排列。

每个结点有一个二元组 \((x,y)\)，笛卡尔树满足只关注 \(x\) 它是一棵二叉搜索树，只关注 \(y\) 它是一个堆。

令 \(l_i\) 表示 \(i\) 结点的左儿子，\(r_i\) 表示 \(i\) 结点的右儿子，如果是小根堆，即 \(x_{l_i}<x_i,x_i<x_{r_i}\) 是第一个条件，\(y_i>y_{l_i},y_i>y_{r_i}\) 是第二个条件。

怎么构建笛卡尔树呢？将二元组按 \(x\) 从小到大排序一个一个插入，发现要满足 \(x\) 的条件，就得保证当前这个二元组能从新树的根一直往右儿子走走到。

用栈维护从根开始一直往右儿子走直到不存在右儿子的这样一条链的 \(y\) 值。显然，栈中的 \(y\) 单调递增。

当插入 \((x_i,y_i)\) 时，找到第一个小于 \(y_j<y_i\) 的结点 \(j\)，将 \(i\) 接到 \(j\) 的右儿子处。

如果 \(j\) 原先就有右儿子 \(k\) 的话，就将 \(k\) 接到 \(i\) 的左儿子处，显然这是合法的。

可以发现，因为每步操作都是唯一的，所以最终的笛卡尔树也是唯一的。

---

笛卡尔树有什么性质？

• 它的中序遍历是原序列（废话）
• 以 \(x\) 为下标的序列上 \(y\) 的 RMQ 是笛卡尔树上 LCA 处的 \(y\) 值。

内容总结

以上是互联网集市为您收集整理的笛卡尔树复习笔记全部内容，希望文章能够帮你解决笛卡尔树复习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---