笛卡尔树就是你给两维限制，一维堆R，一维二叉搜索树K，平地拔起一棵Treap，最广范的应用：用LCA求区间最值，建Treap，还有个什么范围top k我表示并不会查都查不到。它最妙最高的地方在于用栈来建树：我们可以先排序K然后一个个插入，那么我们都是最右端，横容易被卡，那么我们不从上到下，我们从下到上，用栈维护，那就把时间复杂度从O(n^2)降到O(n)，具体过程见下图从图一到图二就是这么一个过程，我们在把K为13的点插入时要找到一个合适的位置，上比他大，下比他小（假设大根堆）笛卡尔树就是你给两维限制，一维堆R，一维二叉搜索树K，平地拔起一棵Treap，最广范的
阅读背景：
[COGS 2421] [HZOI 2016] 简单的Treap 笛卡尔树_weixin_30664615的博客
来源：互联网
分享到：
