Splay是一個二叉平衡樹，可以維護序列，支持在其中插入和刪除。

關鍵操作：rotate，即旋轉，可以更換子樹的根。分為左旋和右旋。splay通過不斷地將新加入的節(jié)點旋轉到根來保證期望深度為log。經(jīng)過發(fā)展，rotate函數(shù)在代碼內(nèi)已經(jīng)非常的簡潔，將左旋和右旋合并為一個函數(shù)（關鍵在于用k存儲x為y的左兒子還是右兒子，運用異或表示“另一個兒子”）。rotate更新父母和孩子的順序：zy->zx,xa->ya,yx->xy，要牢記。旋轉的過程中平衡樹的中序遍歷是不變的。

splay函數(shù)是核心操作。splay(x,k)表示把x旋轉到k的下面。k一般是0或者根節(jié)點。splay過程中關注x的父親（y）和y的父親（z）。如果xyz在一條直線，則先旋轉y再轉x。否則轉兩次x。不這樣做會被構造數(shù)據(jù)卡掉。

splay的節(jié)點可以維護標記。像線段樹那樣下傳即可。pushdown在遞歸前必須寫。pushup在函數(shù)結尾寫。注意pushup的順序。該pushdown的時候一定要pushdown。

insert的時候，初始時要滿足堆的性質(zhì)。如果題目中的操作會改變堆的性質(zhì)，可以隨便插。如果不會改變。如《郁悶的收納員》，不管怎樣都會滿足堆的性質(zhì)，還會利用到它，則要保證插入順序。所以盡量保證堆的性質(zhì)。

getk時先pushdown！注意跳右兒子時先改k再改nw。

插入?yún)^(qū)間，先找到插入位置的后繼，然后將插入位置旋轉到根，后繼旋轉到根下面，左兒子便是空的，可以直接插入你構造的區(qū)間的二叉樹。刪除區(qū)間同理，不過要找到兩端的前驅(qū)后繼。為了防止越界，可以再0、n+1的位置設置“哨兵”，值為極值。不過處理的時候要特別留意它們。