[ Big Interger ] 大數模板

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

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

以下是大數模板:

[ AVL Tree ] 優化AVL樹

AVL樹是以子樹的高度做為平衡的條件
其平衡條件為:
     左子樹的高度與右子樹的高度差不能超過1

因為每次的插入及刪除都有可能壞平衡，所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法，一序為 : 左左、左右、右右、右左，若想知道關於如何進行平衡的介紹請點擊這裡，其插入刪除常數較大，故其平均效率比Size Balanced Tree要差。

因為在網路上看到很多的AVL樹，其寫法都過於冗長，所以我這邊發一個AVL樹的模板，其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數，插入和刪除完後呼叫即可。

以下為模板:

Treap 模板

這是 旋轉式Treap 的模板，是目前所有平衡樹中code最為簡便的一種。
插入和刪除的時間複雜度跟Randomized binary search tree一樣，是在演算法競賽中最適合使用的平衡樹。
因為 分裂/合併式 Treap 可以完全被 分裂/合併式 Randomized binary search tree取代，故不提供

做法1，完全依靠旋轉進行平衡(刪除速度較慢):

作法2，刪除時合併左右子樹(刪除速度較快):

[ 線性同餘方法 ] 亂數產生器 實做

今天來講幾個簡單的亂數產生方法
主要是利用線性同餘方法來處理的

它的首要條件便是必須符合平均分配率Uniform distribution，也就是在$0 \sim m-1$之間的每個數字, 出現的機率必須相等。
Linear Congruential Method雖是常用法，但也有它的條件:
$X(n+1) = (a \times X(n) + c) \%m$，其中$\%$是取餘數的意思
$X(n+1)$為新的亂數，$X(n)$為前一次產生的亂數。則各參數必須符合下列條件:

1. $c$與$m$必須互質。
2. 對於任何$m$的質因數$p$，也必須為$a-1$的質因數。
3. 若$m$為$4$的倍數，則$a-1$也必須為4的倍數。

如此才能確保產生出來的亂數符合平均分配率，同時也具有最長的重複週期。

以下是在網路上找到的一些不錯的亂數產生方法:
其中random1是Brain大神在處理randomize binary tree的亂數(0xdefaced是質數，defaced是英文單字比較好記)
random2聽說是stdlib裡面的rand()原型，而16807是7的5次方，random2可以產生較rand()大的亂數
random4不是線性同於方法，個人覺得他比較像Subtract with carry的方法
在做[分裂/合併式]randomize binary tree時，其實可以利用seed++的方式當作亂數用(連結中有教學)

c++ rope 基本應用

rope(粗繩)是一個很強大的字串處理物件，聽說是為了與string(細繩)做對比才叫做rope的，其底層是一棵持久化平衡樹，因此在做合併或在中間插入的期望時間是logn

再使用rope前必須在前置作以下的處理

#include<ext/rope>
using namespace __gnu_cxx;

定義一個元素為char的rope:

rope<char> r;

其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:

crope r;

當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)

對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀

Randomized Binary Search Tree 平均深度證明

一棵Randomized Binary Search Tree ，平均深度為2logn
其每個節點成為該顆子樹的根的機率有1/(該顆子樹的大小+1)
對於[分裂/合併式][Split / Merge] Randomized Binary Search Tree 亦同
而其等價於在BST中進行隨機插入
這裡提供嚴謹的證明 連結
以下簡略的證明原自於陳柏叡大大(數奧國手)親筆所寫:

現在總共有n個數，要證說對他隨機排序之後一個一個插入BST得到的平均最大深度=2logn。
那看任意一個數x，他的祖先個數就是它的深度，所以只要算x的祖先個數的期望直。
這只要算，對x以外的每個數y，y當x的祖先的機率是多少，再把他們加起來即可。

但注意到，假設在這n個數(由小到大)排序好的序列裡面，x 排在第 i 個， y 排在第 j 個(  y 可以 <x，所以 j 可以 < i  )，那麼落在 [ i , j ] ( 或 [ j , i ] )這個區間裡的所有數， y 是第一個被插入BST的(否則會和 y 是 x 的祖先矛盾)，而這件事情發生的機率為 1/(  | i - j | +1 ) 。
也就是，如果一個數 y 和 x 在排序好的序列裡面的坐標差 = d 的話，那麼 y 當 x 的祖先的機率就是 1/(d+1)。

所以如果 x 是排序好的序列裡的第 i 個，那所求是
1 / i + 1 / ( i - 1 ) + ... + 1/2 + 1/2 + 1/3 + ... + 1/( n - i + 1 )
<= 2 ( 1/2 + 1/3 + ... + 1/n )
約 = 2logn

[smart pointer] [reference counter] 智能指標 引用計數

鑒於有些題目需要記憶體的限制，因此必須要考慮到記憶體的管理。
而智能指標可以幫助我們解決這個問題

在C++11，STL已經有內件shared_ptr，但是速度很慢，而大部分在比賽時會用到的只有引用計數的概念(可以參考Brain大神的blog)，因此我將引用計數(參考自 C++ Template 侯捷譯)部分特別獨立出來，做了一份模板

以下為模板:
用法:

reference_pointer<int> a;//建立一個int的引用指標a
a = new_reference(5);//a指向新增int動態變數，其值為5
a = new_reference<int>(5);//同上，只是定義較為嚴謹
a = new_reference((int)5);//同上，只是定義較為嚴謹
reference_pointer<int> b = a;//將b指向a所指向之物

struct P{
     int a,b;
     P(int _a,int _b):a(_a),b(_b){}
}p(2,3);
reference_pointer<P> a;//建立一個P的引用指標a
c = new_reference(P(1,2));//指向新增P動態變數，其值為1,2
c = new_reference<P>(P(1,2));//同上，只是定義較為嚴謹
c = new_reference(p);//指向新增P動態變數，其值為p

其他的用法可以由下面的代碼看出來(HOJ Problem : 226 - K. CP AC代碼):
其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹