[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree

今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap，可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導，請參考其網站

寫起來並不會比需要旋轉的難
先定義他的節點:
可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)

計算節點大小

主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):
這是將o按中序將前k個節點分到a，剩下的分到b

合併(參見 treap合併):
這就是隨機的精華所在
每次merge時，a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:
但是看了丁安立魔法師的blog，發現只要x++就好了，也不知道為甚麼

如果只是要做普通的二分搜尋樹，可以利用排名來求出其在整顆樹中的名次，然後再相對應處做插入
插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理

旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢)，那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護

像是區間的最大最小值，區間反轉啦，區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情，他都能做到，可以用它來解決很複雜的區間處理問題

注意的是，在有懶惰標記的情況下，如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問，否則懶惰標記可能沒有被推下去，範例如下:

這個範例up()跟down()也要重寫:

因為應用時分靈活，故不提供樣板，只做介紹