splay樹首先是個平衡樹，那麼什麼是平衡樹呢？
平衡樹都是可以保證高度的二叉搜索樹。
但是splay和avl樹/紅黑樹等不同的是，他是均攤復雜度的。類似於並查集。
在觀看本文章前請確保你瞭解過二叉搜索樹Pecco：算法學習筆記(45): 二叉搜索樹
當然如果splay隻是個平衡樹的話，就很沒意思瞭。
splay也可以進行類似於線段樹的操作，區間加區間查詢。而且還有一個操作是線段樹做不到的，那就是區間翻轉。
這裡推薦閱讀嚴格鴿：什麼是權值線段樹 —— 用線段樹來實現平衡樹
首先，splay是個“旋轉樹”，什麼是旋轉呢？
就是我們在插入二叉搜索樹的時候，可能會出現一條很長的鏈。
那麼我們就通過旋轉，使得他變得高度低一些。
值得註意的是
旋轉不會改變中序遍歷的結果
旋轉不會改變中序遍歷的結果
旋轉不會改變中序遍歷的結果
因為二叉搜索樹是有序的，中序遍歷就是排序後的結果，顯然中序遍歷不會發生改變。
那麼splay是怎麼旋轉的呢？
當插入一個節點後，我們就將這個節點變成根節點。
這個就是瞎畫的，不是真的會旋轉成這個樣子
但是！一般的旋轉，我們稱其為“單旋”，一條鏈“單旋”後還是一條鏈。
所以splay使用的是“雙旋”。但是你可能會感覺，就算是這樣“雙旋”，為什麼可以保證復雜度呢？
這個就是個比較復雜度的證明瞭。
伸展樹（Splay）復雜度證明 – Mr_Spade – 博客園
所以這裡我們就把他當成黑盒來用就可以瞭（畢竟並查集的復雜度我們也不會證明
那麼我們這裡放上板子
這裡 rm ch[x][0/1] 表示 x 的左右兒子
rm rt 根節點是哪個
rm siz[x] 表示 x 的子樹大小
rm val[x] 表示 x 節點上的值
rm cnt[x] 表示 val[x] 在 x 上出現瞭多少次
rm fa[x] x 的父親節點
rm splay(x,y) 可以將節點 x 旋轉到 y 的子節點上
僅供理解，並不是真的旋轉成這個樣子
rm pushup(x) 更新點 x 的子樹大小
這裡不需要關心 rm rotate ,get ,splay 三個函數，當成黑箱就可以瞭。
void push_up(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x]; }
bool get(int x) { return x == ch[fa[x]][1]; }
void clear(int x) {
ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;
}
void rotate(int x) {
int y = fa[x], z = fa[y], chk = get(x);
ch[y][chk] = ch[x][chk ^ 1];
if (ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
ch[x][chk ^ 1] = y;
fa[y] = x;
fa[x] = z;
if (z) ch[z][y == ch[z][1]] = x;
push_up(y);
}
void splay(int x, int goal) {
for (int f = fa[x]; (f = fa[x]) != goal; rotate(x))
if (fa[f] != goal) rotate(get(x) == get(f) ? f : x);
if (goal == 0)rt = x;
}
