[ Splay Tree ] 伸展樹模板

最近研究了伸展樹，它可以在均攤\(\ord{logN}\)的時間完成伸展操作，所謂的伸展操作就是將某個節點旋轉(rotate)到根(root)的過程，因為我們大部分在搜尋資料時，常常都只會用到特定的資料，其他大多數的資料是較少被搜尋的，因此將常被搜尋的資料靠近根是很好的策略，伸展樹由此被發明。
因為伸展樹可以分裂合併，所以可以取代分裂合併式treap或是分裂合併式randomize binary tree的功能，可以在競賽中被使用，而普通的伸展樹效率不高，故本文只介紹作區間處理的伸展樹
之後的link-cut tree會用到他，所以必須要能理解
例題: UVA 11922

定義伸展樹節點:(T為資料型態)

初始化時nil的l,r要指向自己

旋轉(跟其他樹差不多)
d=0左旋,1右旋

接下來是最重要的伸展操作
這是按劉汝佳在橘色那本書的寫法實現的
主要是將第k個節點伸展到root的過程
注意!! k必須大於0

有了splay操作，接下來是分裂&合併

當我們要維護一個區間1~n時，可以建立0~n的splay tree，0是廢棄節點，較為方便使用

最後提供新增節點的方法:

這樣所有的操作就齊全了
剩下的一些懶惰標記跟treap一樣，可以做區間翻轉和線段樹的功能
但是請小心指標的使用
(nil為衛兵指標，方便用來編輯，若不想用可以將程式碼略為修改)