[ basic operation of naive order statistic tree ] 樸素二元搜尋樹 名次樹的基本操作

一般的名次樹支援以下幾種操作:

1.插入
2.刪除
3.查找
4.求節點大小
5.求元素名次
6.求第k大
7.求前驅
8.求後繼

之前寫的模板已經有了前六種操作，因此我會在本模板中附上求前驅跟後繼的操作
前驅與後繼並不是名次樹才有的操作，在不記錄節點大小的情形下也能求得
關於求前驅跟後繼操作的說明可以參考 随机平衡二叉查找树Treap的分析与应用 這篇文章

以下提供模板:

[ AA tree ] AA樹

AA樹是紅黑樹的一種變種，是Arne Andersson教授在1993年年在他的論文"Balanced search trees made simple"中介紹，設計的目的是減少紅黑樹考慮的不同情況。區別於紅黑樹的是，AA樹的紅結點只能作為右葉子。另外AA樹為實現方便，不再使用紅黑兩種顏色，而是用level標記結點，結點中的level相當於紅黑樹中結點的黑高度。

其主要透過skew和split兩種旋轉來進行平衡的，插入時只能為紅節點，故會出現不符合其規定則進行平衡操作

若想進一步了解其平衡操作請參考維基百科
在實作中，skew為右璇，split為左旋。本模板以rotate(o,0)、rotate(o,1)代表

以下提供模板:

[ symmetric binary B-tree ( red black tree ) ] 對稱二叉B樹 ( 紅黑樹 )

紅黑樹是一種有最壞情況擔保的平衡樹，其插入最多會用到2個旋轉，刪除最多用到3個旋轉，其犧牲些許的平衡來加快插入刪除的速度，並有高度上h<=2*log(n+1)的保證。
故其插入刪除之常數會比較小，而查詢之常數會較大(相對於一般高度平衡樹)，而一般的函式庫裡的"關聯數組"通常適用紅黑樹實做的
其平衡原因及方法請參考維基百科
因其操作複雜故不常在競賽中被使用，且刪除速度較size balanced tree慢約2倍

以下提供模板:

[ scapegoat tree ] 替罪羊樹

替罪羊樹論文其中一個作者，Ronald Linn Rivest，同時也是RSA加密算法的R
替罪羊樹是一種不需要旋轉的平衡樹，它會要求使用者給定一個\(\alpha\)值，其值介於0.5到1之間，\(\alpha\)越大，插入就越快，查詢就越慢，實驗發現\(\alpha\)介於0.55~0.75是最佳的，但是具體的值要看使用者的要求
其平衡滿足:
1.
    \(\alpha*size(o) \le size(o \to left)\)
    \(\alpha*size(o) \le size(o \to right)\)
2.
    \(deep(o) \le log_{1/\alpha} (size(tree))\)
當插入節點導致條件2.不滿足時，會往上回溯到第一個不滿足的節點，然後重建這顆節點的子樹成為完美平衡的二元樹
刪除可以用一般的BST刪除法，當不滿足條件時往上回溯到最先不滿足的節點，重建子樹，也可以懶惰刪除，先設立一個標記， 要刪除這個節點就把它做記號，當\(\alpha\)*全部的節點數量>實際上存在的節點數量，就重建這顆子樹
本文提供一般刪除的方法

其實替罪羊樹的節點是不需要記錄其size的，因為若需要重建，求得size的時間複雜度與重建的時間複雜度相等，這裡為了支援其它有如rank等操作才將size域附加在節點中

插入刪除的均攤時間複雜度為\(\ord{logN}\)，相較之下朝鮮樹只是他的劣質仿冒品，其複雜度證明請參考此論文

以下為模板:

這裡也提供不需要記錄節點大小(size)的平衡方式，相對的一些需要用到附加size域的函數將不能被使用，但插入刪除的效率不變


如果編譯發現沒有__lg()這個函數的話，請在程式碼開頭附上這份code:

[ korea tree ] 朝鮮樹

某天albus YY出來了一個沒有旋轉操作的平衡樹，由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席，所以就叫朝鮮樹了！

朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹，利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為\(\ord{N*sqrt(N)}\)，是一種很糟糕的平衡樹，但是我們還是要理解他，因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用

所有操作都與本篇其他樹差不多只多了個rebuild函數，它會暴力將整顆樹重建成深度logN的平衡樹

對於重建的部分則使用了拍扁重建法，將樹先拍扁成鍊表後重建，只需要花費\(\ord 1\)的空間複雜度

以下提供模板:

[ 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為衛兵指標，方便用來編輯，若不想用可以將程式碼略為修改)

[ Big Interger ] 大數模板

今天在家裡寫了一整天的大數，好不容易加減乘除都有了，但是乘法的部分FFT還不會寫所以先用做基本的n^2乘法(聽說有一個奇怪的方法叫做Karatsuba演算法也能做大數乘法，還蠻快的)

定義一個大數:
bigN a;//定義大數

以下是大數模板: