<style> .reveal .slides { text-align: left; font-size:30px } </style> # treap Competitive programming 2 2022/1/3 --- ## 樹堆(Treap) Treap是一顆平衡二元樹 Treap = tree(二元樹) + heap(堆積) 每個節點有兩個重要的值：key, priority key用於存值，priority用來維護treap的平衡 ```cpp= struct Treap{ int key,pri,sz; //key,priority,size Treap *l, *r; //左右子樹 Treap(){} Treap(_key){ key = _key; pri = rand(); //隨機的數維持樹的平衡 sz = 1; l = r = nullptr; } } ``` ---- Treap滿足以下性質 1. 左子樹的 key 小於等於自己，右子樹的 key 大於等於自己(tree) 2. 父節點的 priority 大於其子節點的 priority (heap) 3. 左右子樹也分別是一顆treap 4. 給定 n 個節點的 key,priority 的大小關係，那麼這棵 treap 的形狀唯一。  ---- 做法 Treap分為旋轉式跟非旋轉式 這邊會介紹非旋轉式Treap，也就是merge-split treap 它易實作、期望複雜度好、靈活性高 幾乎每個操作都是 $O(lgN)$ 而主要有兩個函式 - split跟merge split 將一棵treap分成兩顆 merge 將兩棵treap合併成一棵 ---- ## merge-split treap ### merge 將兩棵Treap合併成一棵 (須保證左邊那棵所有的key小於等於右邊那棵) <div style="margin-left:-140px"> ```cpp= int Size(Treap* x){ return x ? x->sz : 0 ; } void pull(Treap *x){ x->sz = Size(x->l) + Size(x->r) + 1;} Treap* merge(Treap *a,Treap *b){ if(!a || !b) return a ? a : b; //其中一個子樹為空則回傳另一個 if(a->pri > b->pri){ //如果a的pri比較大則a比較上面 a->r = merge(a->r,b); //將a的右子樹跟b合併 pull(a); return a; } else{ //如果b的pri比較大則b比較上面 b->l = merge(a,b->l); //將b的左子樹根a合併 pull(b); return b; } } ``` </div> ---- ## merge-split treap ### split by key 將一棵Treap分成兩棵， key小於等於k的分到左邊那棵a，其他分到右邊那棵b <div style="margin-left:-140px"> ```cpp= void splitByKey(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } else if(x->val<=k){ a = x; splitByKey(x->r, k, a->r, b); pull(a); } else{ b = x; splitByKey(x->l, k, a, b->l); pull(b); } } ``` </div> ---- ## merge-split treap ### split by k-th 將一棵Treap分成兩棵， 左邊那棵a的節點數有k個，右邊那棵b節點數為n-k個 <div style="margin-left:-140px"> ```cpp= void splitByKth(Treap *x,int k,Treap*& a,Treap*& b){ if(!x){ a = b = nullptr; } else if(Size(x->l) + 1 <= k){ a = x; //如果左子樹+自己的size小於等於k則左子樹跟自己為k個以內 splitByKth(x->r, k - Size(x->l) - 1, a->r, b); pull(a); } else{ b = x; //如果左子樹+自己的size大於k個則右子樹跟自己會分到右邊 splitByKth(x->l, k, a, b->l); pull(b); } } ``` </div> ---- 有以上split跟merge操作之後就可以完成大部分了! 像是插入元素或刪除都是在split和merge的基礎下操作 (記得左右順序要處理好!) <div style="margin-left:-165px"> ```cpp= void insert(int val){ //新增一個值為val的元素 Treap *x = new Treap(val); //設一個treap節點 Treap *l,*r; splitByKey(root, val, l, r); //找到新節點要放的位置 root = merge(merge(l,x),r); //合併到原本的treap裡 } void erase(int val){ //移除所有值為val的元素 Treap *l,*mid,*r; splitByKey(root, val, l, r); //把小於等於val的丟到l splitByKey(l, val-1, l, mid); //小於val的丟到l,等於val的就會在mid裡 root = merge(l,r); //將除了val以外的值合併 } ``` </div> ---- ## 複雜度分析 | build | split | merge | | --------- | -------- | -------- | | $O(NlgN)$ | $O(lgN)$ | $O(lgN)$ | <!-- [sample code](https://github.com/jakao0907/contest/blob/master/dataStructure/treap_split_key%26kth.cpp) --> ---- <div style="text-align:left;font-size:26px"> ### Treap and 懶標記 treap在處理序列問題非常強大像是以下題目 兩種操作： 1. 翻轉區間[l,r] 2. 詢問第i格的值 我們可以用treap儲存序列 如果要翻轉一段區間則是將一棵treap交換他的左右子樹，並且他的所有子樹每個節點都交換左右子樹，就能達到翻轉區間 顯然，如果每次翻轉操作直接硬做，複雜度會爛掉 所以我們可以用一個懶標記，把要翻轉的區間記起來，下次走到再反轉，則複雜度就會降到好好的 $O(lgN)$ ```cpp= //記得在Treap結構裡加入變數tag void push(Treap* x){ if(x->tag){ //如果區間要翻轉 swap(x->l,x->r); //交換左右子樹 if(x->l) x->l->tag ^= 1; //加tag到左子樹 if(x->r) x->r->tag ^= 1; //加tag到右子樹 x->tag = NO_TAG; } } ``` </div> --- ## Question Time and Practice [Homework Link](https://vjudge.net/contest/475226) 提交期限到下星期一 1/10 23:59 截止