首页 > 代码库 > [平衡树学习笔记]那些你所不知道的鬼畜写法

[平衡树学习笔记]那些你所不知道的鬼畜写法

2024-07-16 16:17:23   215人阅读

treap:  (Orz fhq 大神，我曾经以为我会了 treap ，就再也不会写 splay 了，然后我遇上了 lct )

 

 1 #include <cstdlib> 2 const int sizeOfMemory=10000; 3 template <class type> inline void swap(type & x, type & y) {type t=x; x=y; y=t;} 4  5 namespace treap 6 { 7     struct node 8     { 9         int key, size;10         short weight;11         bool rev;12         node * left, * right;13         inline node():size(1), weight(0) {left=right=this;}14         inline void maintain() {size=left->size+right->size+1;}15         inline void pushdown() {if (rev) swap(left, right), left->rev^=1, right->rev^=1, rev=0;}16     };17     node * null=new node();18     node memory[sizeOfMemory], * portOfMemory=memory;19 20     inline node * newnode(int key)21     {22         node * ret=portOfMemory++;23         ret->key=key; ret->size=1;24         ret->weight=rand();25         ret->rev=0;26         ret->left=ret->right=null;27         return ret;28     }29     void splitBySize(node * t, int k, node *& l, node *& r)30     {31         if (t==null) l=r=null;32         else33         {34             t->pushdown();35             if (t->left->size<k)36             {37                 l=t;38                 splitBySize(t->right, k-t->left->size-1, t->right, r);39                 l->maintain();40             }41             else42             {43                 r=t;44                 splitBySize(t->left, k, l, t->left);45                 r->maintain();46             }47         }48     }49     void splitByKey(node * t, int k, node *& l, node *& r)50     {51         if (t==null) l=r=null;52         else53         {54             t->pushdown();55             if (t->key<k)56             {57                 l=t;58                 splitByKey(t->right, k, t->right, r);59                 l->maintain();60             }61             else62             {63                 r=t;64                 splitByKey(t->left, k, l, t->left);65                 r->maintain();66             }67         }68     }69     node * merge(node * l, node * r)70     {71         if (l==null) return r;72         if (r==null) return l;73         if (l->weight>r->weight)74         {75             l->pushdown();76             l->right=merge(l->right, r);77             l->maintain();78             return l;79         }80         else81         {82             r->pushdown();83             r->left=merge(l, r->left);84             r->maintain();85             return r;86         }87     }88 }
本傻装B系列

 

splay:  (我曾经以为我会了 treap ，就再也不会在 lct 外的地方写 splay 了，然后我遇上了 自顶向下 splay )

 

等待完坑

 

AVL:  ( fhq 大神 说是为了解决人工实现 rope 时，treap 不能直接复制节点否则权重会痿掉的问题而搞出来的新产物，但 clj 大神似乎有更高明的做法)

 

等待完坑


联系
我们