数据结构线性构造treap

treap的线性构造可以使复杂度锐减到\(O(n)\)，很优秀

treap的本质就是小根堆+二叉搜索树，即保证val满足搜索树的同时，维护rad的小根堆。

现在我们先把数据预处理一下，按val值升序排序。那么我们不必再关系val，专注于rad即可

先考虑一个特殊情况，假如数据恰好也满足rad的升序，那么我们就一次插到每个节点的右儿子处

这时候假如插进来个节点比较特殊，它的rad比较小ヽ(*。>Д<)o゜那么...

有点类似于新节点把原节点打到了左边，自己取而代之。

这样的做法的正确性是可以保证的:val上，新插的节点的左儿子val比自己小，本身作为右儿子..；rad上，也满足了小根堆

剩下的继续即可：

这样不断地打骨折、接上、打骨折、接上..即可线性构造一颗treap

兼容性极差的代码：

stack <int> tmp;

        for(int i=1;i<=len;++i){

            int j=0,now=newnode(read());

            while(!tmp.empty()&&rad[now]<rad[tmp.top()]){

                ch[tmp.top()][1]=j;

                j=tmp.top();

                updata(j);

                ch[now][0]=tmp.top();

                tmp.pop();

            }

            updata(now);

            if(!tmp.empty()) ch[tmp.top()][1]=now,updata(tmp.top());

            tmp.push(now);

        }

        int u;

        while(!tmp.empty()) u=tmp.top(),updata(u),tmp.pop();

巴特西

线性构造treap

数据结构线性构造treap

最新文章

热门文章

巴特西

线性构造treap

数据结构 线性构造treap

最新文章

热门文章

数据结构线性构造treap