笛卡尔树学习笔记

数据结构

世人的烦恼多来源于书读的不多。

却想的太多。

——杨绛

笛卡尔树：

笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的，从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知，笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。[From 百度]

定义:

• 每个节点有两个值,Key和Value
• 光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大
• 光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要小（或者大）。

构造：

• 我们维护笛卡尔树的极右链，就是根，根的右儿子，根的右儿子的右儿子…….
• 放在一个栈里，栈底是根，这样很显然从栈顶到栈底，val值是不断变小的。
• 每当我们进入一个新的节点，我们从栈顶开始找，当找到第一个节点的val值比我小，那么我必须得是它的儿子，而我的key值又比他大，所以我作为它的右儿子，而原先它的儿子key值比我小，所以作为我的左儿子，
• 这样就维护了一个treap的性质，然后原来那个点变为了我的左儿子，所以就要从极右链中删掉，我加入到极右链中，这样每个点进栈一次，出栈一次，复杂度就是O(n)的，下面贴出具体的代码。

for (int i=1;i<=n;i++){
        read(key[i]),val[i]=rand();
        while (top&&val[i]<val[stack[top]]){
            lson[i]=stack[top];
            top--;
        }
        if (top) rson[stack[top]]=i;
        stack[++top]=i;
    }

用处：

主要用于$Treap$的构建
当题目Key给定时，用普通方法构造$Treap$一些数据可以把树高卡成$O(n)$，复杂度变为$O(n^2)$而此时用笛卡尔树的构造方法为稳定$O(nlogn)$

同时在构造$FHQ Treap$时也需要用笛卡尔树的构建方法，因为非旋转式Treap的$ist()$需要一次$split()$和两次$merge()$，常数略大，用笛卡尔树建树比较快。