本篇尚在施工中...
Treap 可以做到很多酷酷的序列操作。本篇主要討論 Split/Merge Treap。
基礎概念
- key 決定左右順序，pri 值決定上下順序
Treap 是一棵二元樹，每個節點都包含 key 和 pri 值， 並且符合性質 1. 左子樹的 key 都小於自己，右子樹的 key 都大於自己；2. 子節點的 pri 都比父節點大
只要透過 key 和 pri 便能唯一決定這棵樹的長相
- 以透過 split(u,k) 和 merge(a,b) 操作樹
split(u,k) 將一棵 Treap 分成兩棵，其中一棵鍵值皆小於 k，另一棵鍵值皆大於 k merge(a,b) 將兩棵 Treap 合併，其中一棵鍵值皆小於 k，另一棵鍵值皆大於 k（和 split 為反操作）
只要好好遵守函數定義，我們可以在不破壞 Treap 性質的條件下對他動手動腳：
想要插入，就把一顆 treap 切開後，把東西塞進去，再 merge 回去 想要刪除，就把一顆 treap 切兩刀，丟掉中間，再 merge 回去
- key 和 pri 塞入不同數字，樹的意義會不同。
key 和 pri 可以自己賦予意義，例如：
key = index, pri = value：得到一顆笛卡爾樹。 key = value, pri = random：可以支援動態排序 key = index, pri = random, data = value：拿來維護序列（data 為無關乎樹的長相，節點內存的資料）
- 採用隨機的 pri 值，防止退化
不管是 split、merge、在樹上查找，複雜度都與深度相關。
Treap 的精髓在於，採用隨機的 pri 值，使整顆樹的期望深度為 \(logn\)，複雜度更好。
- 以維護 size 代替 key = index
拿 Treap 來維護序列是很常見的用法，但想像一下插入節點的過程。 我們需要把插入位置前、後的 key 值都做改變，顯得非常麻煩。
把 key 丟棄不用，反正只要再 split 和 merge 的時候，保證兩棵 treap 是不相交的連續區間，並且知道大小關係就好了。
但把 key=index 丟棄之後，要怎麼知道這個節點是第幾個？ 維護每個節點的 size，這樣在搜下去的過程中，就能算出這個節點的 index
如下圖，節點 3 的 index 為 6：
實作
- 判斷當前節點是不是答案、要不要被包括進分割
動態排序
get_rank(x)，有幾個數字小於x，每次插入、刪除自己找出目標位置insert(x)erase(x)