[ Big Interger ] 大數模板

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

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

以下是大數模板:

	#include<algorithm>
	#include<iostream>
	#include<sstream>
	#include<iomanip>
	#include<vector>
	#include<string>
	#include<cmath>
	using namespace std;
	template<typename T>
	inline string to_string(const T& x){
	stringstream ss;
	return ss<<x,ss.str();
	}
	typedef long long LL;
	struct bigN:vector<LL>{
	const static int base=1000000000,width=log10(base);
	bool negative;
	bigN(const_iterator a,const_iterator b):vector<LL>(a,b){}
	bigN(string s){
	if(s.empty())return;
	if(s[0]=='-')negative=1,s=s.substr(1);
	else negative=0;
	for(int i=int(s.size())-1;i>=0;i-=width){
	LL t=0;
	for(int j=max(0,i-width+1);j<=i;++j)
	t=t*10+s[j]-'0';
	push_back(t);
	}
	trim();
	}
	template<typename T>
	bigN(const T &x):bigN(to_string(x)){}
	bigN():negative(0){}
	void trim(){
	while(size()&&!back())pop_back();
	if(empty())negative=0;
	}
	void carry(int _base=base){
	for(size_t i=0;i<size();++i){
	if(at(i)>=0&&at(i)<_base)continue;
	if(i+1u==size())push_back(0);
	int r=at(i)%_base;
	if(r<0)r+=_base;
	at(i+1)+=(at(i)-r)/_base;
	at(i)=r;
	}
	}
	int abscmp(const bigN &b)const{
	if(size()>b.size())return 1;
	if(size()<b.size())return -1;
	for(int i=int(size())-1;i>=0;--i){
	if(at(i)>b[i])return 1;
	if(at(i)<b[i])return -1;
	}
	return 0;
	}
	int cmp(const bigN &b)const{
	if(negative!=b.negative)return negative?-1:1;
	return negative?-abscmp(b):abscmp(b);
	}
	bool operator<(const bigN&b)const{return cmp(b)<0;}
	bool operator>(const bigN&b)const{return cmp(b)>0;}
	bool operator<=(const bigN&b)const{return cmp(b)<=0;}
	bool operator>=(const bigN&b)const{return cmp(b)>=0;}
	bool operator==(const bigN&b)const{return !cmp(b);}
	bool operator!=(const bigN&b)const{return cmp(b)!=0;}
	bigN abs()const{
	bigN res=*this;
	return res.negative=0, res;
	}
	bigN operator-()const{
	bigN res=*this;
	return res.negative=!negative,res.trim(),res;
	}
	bigN operator+(const bigN &b)const{
	if(negative)return -(-(*this)+(-b));
	if(b.negative)return *this-(-b);
	bigN res=*this;
	if(b.size()>size())res.resize(b.size());
	for(size_t i=0;i<b.size();++i)res[i]+=b[i];
	return res.carry(),res.trim(),res;
	}
	bigN operator-(const bigN &b)const{
	if(negative)return -(-(*this)-(-b));
	if(b.negative)return *this+(-b);
	if(abscmp(b)<0)return -(b-(*this));
	bigN res=*this;
	if(b.size()>size())res.resize(b.size());
	for(size_t i=0;i<b.size();++i)res[i]-=b[i];
	return res.carry(),res.trim(),res;
	}
	bigN operator*(const bigN &b)const{
	bigN res;
	res.negative=negative!=b.negative;
	res.resize(size()+b.size());
	for(size_t i=0;i<size();++i)
	for(size_t j=0;j<b.size();++j)
	if((res[i+j]+=at(i)*b[j])>=base){
	res[i+j+1]+=res[i+j]/base;
	res[i+j]%=base;
	}//乘法用carry會溢位
	return res.trim(),res;
	}
	/* 用二分搜做除法很慢
	bigN operator/(const bigN &b)const{
	bigN res;
	if(size()<b.size())return res;
	if(negative||b.negative){
	res=abs()/b.abs();
	res.negative=negative!=b.negative;
	return res.trim(),res;
	}
	res.resize(size()-b.size()+1);
	for(int i=int(res.size())-1;i>=0;--i){
	int l=0,r=base-1,ans=l,mid;
	while(l<=r){
	res[i]=mid=(l+r)/2;
	if((res*b).abscmp(*this)>0)r=mid-1;
	else l=mid+1,ans=mid;
	}
	res[i]=ans;
	}
	return res.carry(),res.trim(),res;
	}
	/*/
	bigN operator/(const bigN &b)const{
	int norm=base/(b.back()+1);
	bigN x=abs()*norm;
	bigN y=b.abs()*norm;
	bigN q,r;
	q.resize(x.size());
	for(int i=int(x.size())-1;i>=0;--i){
	r=r*base+x[i];
	int s1=r.size()<=y.size()?0:r[y.size()];
	int s2=r.size()<y.size()?0:r[y.size()-1];
	int d=(LL(base)*s1+s2)/y.back();
	r=r-y*d;
	while(r.negative)r=r+y,--d;
	q[i]=d;
	}
	q.negative=negative!=b.negative;
	return q.trim(),q;
	}
	//*/
	bigN operator%(const bigN &b)const{
	return *this-(*this/b)*b;
	}
	friend istream& operator>>(istream &ss,bigN &b){
	string s;
	return ss>>s, b=s, ss;
	}
	friend ostream& operator<<(ostream &ss,const bigN &b){
	if(b.negative)ss<<'-';
	ss<<(b.empty()?0:b.back());
	for(int i=int(b.size())-2;i>=0;--i)
	ss<<setw(width)<<setfill('0')<<b[i];
	return ss;
	}
	template<typename T>
	operator T(){
	stringstream ss;
	ss<<*this;
	T res;
	return ss>>res,res;
	}
	};

view raw bigN.cpp hosted with ❤ by GitHub

[ AVL Tree ] 優化AVL樹

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

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

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

以下為模板:

	#ifndef AVL_TREE
	#define AVL_TREE
	template<typename T>
	class avl_tree{
	private:
	struct node{
	node *ch[2];
	int size;
	char h;
	T data;
	inline void up(){h=ch[ch[0]->h<ch[1]->h]->h+1;}
	node(const T&d):size(1),h(1),data(d){}
	node():size(0),h(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	a->size=b->size;
	b->size=b->ch[0]->size+b->ch[1]->size+1;
	b->up(),a->up();
	}
	inline void balanced(node *&o,bool d){
	if(o->ch[d]->h-o->ch[!d]->h>1){
	node *&t=o->ch[d];
	if(t->ch[d]->h>t->ch[!d]->h)rotate(o,!d);
	else rotate(o->ch[d],d),rotate(o,!d);
	}else o->up();
	}
	void insert(node *&o,const T &data){
	if(!o->size){
	o=new node(data);
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->size++;
	bool d=o->data<data;
	insert(o->ch[d],data);
	balanced(o,d);
	}
	}
	bool erase(node *&o,const T &data){
	if(!o->size)return 0;
	if(o->data==data){
	if(!o->ch[0]->size||!o->ch[1]->size){
	node *t=o;
	o=o->ch[0]->size?o->ch[0]:o->ch[1];
	delete t;
	}else{
	o->size--;
	node *tmd=o->ch[1];
	while(tmd->ch[0]->size)tmd=tmd->ch[0];
	o->data=tmd->data;
	erase(o->ch[1],tmd->data);
	balanced(o,0);
	}return 1;
	}
	bool d=o->data<data;
	if(erase(o->ch[d],data)){
	o->size--,balanced(o,!d);
	return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->size)clear(o->ch[0]),clear(o->ch[1]),delete(o);
	}
	public:
	avl_tree():nil(new node),root(nil){}
	~avl_tree(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	node *o=root;
	while(o->size&&o->data!=data)o=o->ch[o->data<data];
	return o->size;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->size;)
	if(o->data<data)cnt+=o->ch[0]->size+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->size)o=o->ch[0];
	else if(k==o->ch[0]->size+1)return o->data;
	else k-=o->ch[0]->size+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->size;}
	inline int height(){return root->h;}
	};
	#endif

view raw AVL tree.cpp hosted with ❤ by GitHub

Treap 模板

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

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

	#ifndef TREAP
	#define TREAP
	template<typename T>
	class treap{
	private:
	struct node{
	T data;
	unsigned fix;
	int size;
	node *ch[2];
	node(const T&d):data(d),size(1){}
	node():size(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	unsigned x;
	inline unsigned ran(){
	return x=x*0xdefaced+1;
	}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->size=b->size;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->size=b->ch[0]->size+b->ch[1]->size+1;
	}
	void insert(node *&o,const T &data){
	if(!o->size){
	o=new node(data),o->fix=ran();
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->size++;
	bool d=o->data<data;
	insert(o->ch[d],data);
	if(o->ch[d]->fix>o->fix)rotate(o,!d);
	}
	}
	bool success_erase(node *&o){
	if(!o->ch[0]->size||!o->ch[1]->size){
	node *t=o;
	o=o->ch[0]->size?o->ch[0]:o->ch[1];
	delete t;
	}else{
	o->size--;
	bool d=o->ch[0]->fix>o->ch[1]->fix;
	rotate(o,d);
	success_erase(o->ch[d]);
	}
	return 1;
	}
	bool erase(node *&o,const T &data){
	if(!o->size)return 0;
	if(o->data==data)return success_erase(o);
	if(erase(o->ch[o->data<data],data)){
	o->size--;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->size)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	treap(unsigned s=20150119):nil(new node),root(nil),x(s){}
	~treap(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o->size;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->size;)
	if(o->data<data)cnt+=o->ch[0]->size+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->size)o=o->ch[0];
	else if(k==o->ch[0]->size+1)return o->data;
	else k-=o->ch[0]->size+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->size)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->size;}
	};
	#endif

view raw treap1.cpp hosted with ❤ by GitHub

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

	#ifndef TREAP
	#define TREAP
	template<typename T>
	class treap{
	private:
	struct node{
	T data;
	unsigned fix;
	int s;
	node *ch[2];
	node(const T&d):data(d),s(1){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	unsigned x;
	inline unsigned ran(){
	return x=x*0xdefaced+1;
	}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->s=b->s;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	}
	void insert(node *&o,const T &data){
	if(!o->s){
	o=new node(data),o->fix=ran();
	o->ch[0]=o->ch[1]=nil;
	}else{
	o->s++;
	bool d=o->data<data;
	insert(o->ch[d],data);
	if(o->ch[d]->fix>o->fix)rotate(o,!d);
	}
	}
	node *merge(node *a,node *b){
	if(!a->s||!b->s)return a->s?a:b;
	if(a->fix>b->fix){
	a->ch[1]=merge(a->ch[1],b);
	a->s=a->ch[0]->s+a->ch[1]->s+1;
	return a;
	}else{
	b->ch[0]=merge(a,b->ch[0]);
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	return b;
	}
	}
	bool erase(node *&o,const T &data){
	if(!o->s)return 0;
	if(o->data==data){
	node *t=o;
	o=merge(o->ch[0],o->ch[1]);
	delete t;
	return 1;
	}
	if(erase(o->ch[o->data<data],data)){
	o->s--;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	treap(unsigned s=20150119):nil(new node),root(nil),x(s){}
	~treap(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o->s;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->s;)
	if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->s)o=o->ch[0];
	else if(k==o->ch[0]->s+1)return o->data;
	else k-=o->ch[0]->s+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->s;}
	};
	#endif

view raw treap2.cpp hosted with ❤ by GitHub

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

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

它的首要條件便是必須符合平均分配率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的倍數。

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

以下是在網路上找到的一些不錯的亂數產生方法:

	//線性同餘方法
	//這個方法數字很好記
	unsigned random1(){
	static unsigned x=20150118;
	return x=x*0xdefaced+1;
	}
	int random2(){
	static unsigned x=time(0);
	return x=x*16807;//7^5
	}
	// 網路上看到的，用來處理treap的亂數
	int random3(){
	static int x=123456789;
	return x+=(x<<2)+1;
	}
	long long random4(){
	static long long x=323232;
	return x+=x<<2|1;
	}
	//5、6是較快的算法，利用簡單的移位處理
	inline int random5(){
	static int seed=20160424;
	return seed+=(seed<<16)+0x1db3d743;
	}
	inline long long random6(){
	static long long seed=20160424;
	return seed+=(seed<<32)+0xdb3d742c265539d;
	}
	//要記數字太麻煩了而且比較慢，比賽時不要用這種
	int random7(){
	static int x=1;
	return x=x*1103515245+12345;
	}

view raw lehmer random.cpp hosted with ❤ by GitHub

其中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 侯捷譯)部分特別獨立出來，做了一份模板

以下為模板:

	#ifndef REFERENCE_POINTER
	#define REFERENCE_POINTER
	template<typename T>
	struct _RefCounter{
	T data;
	int ref;
	_RefCounter(const T&d=0):data(d),ref(0){}
	};
	template<typename T>
	struct reference_pointer{
	_RefCounter<T> *p;
	T *operator->(){return &p->data;}
	T &operator*(){return p->data;}
	operator _RefCounter<T>*(){return p;}
	reference_pointer &operator=(const reference_pointer &t){
	if(p&&!--p->ref)delete p;
	p=t.p;
	p&&++p->ref;
	return *this;
	}
	reference_pointer(_RefCounter<T> *t=0):p(t){
	p&&++p->ref;
	}
	reference_pointer(const reference_pointer &t):p(t.p){
	p&&++p->ref;
	}
	~reference_pointer(){
	if(p&&!--p->ref)delete p;
	}
	};
	template<typename T>
	inline reference_pointer<T> new_reference(const T&nd){
	return reference_pointer<T>(new _RefCounter<T>(nd));
	}
	#endif

view raw reference_counting.cpp hosted with ❤ by GitHub

用法:

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代碼):

	#include<bits/stdc++.h>
	using namespace std;
	#ifndef REFERENCE_POINTER
	#define REFERENCE_POINTER
	template<typename T>
	struct _RefCounter{
	T data;
	int ref;
	_RefCounter(const T&d=0):data(d),ref(0){}
	};
	template<typename T>
	struct reference_pointer{
	_RefCounter<T> *p;
	T *operator->(){return &p->data;}
	T &operator*(){return p->data;}
	operator _RefCounter<T>*(){return p;}
	reference_pointer &operator=(const reference_pointer &t){
	if(p&&!--p->ref)delete p;
	p=t.p;
	p&&++p->ref;
	return *this;
	}
	reference_pointer(_RefCounter<T> *t=0):p(t){
	p&&++p->ref;
	}
	reference_pointer(const reference_pointer &t):p(t.p){
	p&&++p->ref;
	}
	~reference_pointer(){
	if(p&&!--p->ref)delete p;
	}
	};
	template<typename T>
	inline reference_pointer<T> new_reference(const T&nd){
	return reference_pointer<T>(new _RefCounter<T>(nd));
	}
	#endif
	struct node;
	typedef reference_pointer<node> pt;
	struct node{
	char data;
	int size;
	pt l,r;
	node(const node&t):data(t.data),size(t.size),l(t.l),r(t.r){}
	node(const char &d):data(d),size(1){}
	inline void up(){
	size=1;
	if(l)size+=l->size;
	if(r)size+=r->size;
	}
	};
	inline int size(pt &o){return o?o->size:0;}
	void split(pt o,pt &a,pt &b,int k){
	if(!o)a=b=0;
	else{
	o=new_reference(*o);
	if(k<=size(o->l)){
	b=o;
	split(o->l,a,b->l,k);
	}else{
	a=o;
	split(o->r,a->r,b,k-size(o->l)-1);
	}
	o->up();
	}
	}
	pt merge(pt a,pt b){
	if(!a||!b)return a?a:b;
	static int x;
	if(x++%(a->size+b->size)<a->size){
	a->r=merge(a->r,b);
	a->up();
	return a;
	}else{
	b->l=merge(a,b->l);
	b->up();
	return b;
	}
	}
	pt build(char *s,int l,int r){
	int mid=(l+r)>>1;
	pt k=new_reference(node(s[mid]));
	if(l<=mid-1)k->l=build(s,l,mid-1);
	if(mid+1<=r)k->r=build(s,mid+1,r);
	k->up();
	return k;
	}
	void dfs(pt&t){
	if(!t)return;
	dfs(t->l);
	putchar(t->data);
	dfs(t->r);
	}
	char s[1000005];
	pt root;
	pt a,b,c,d,e,f;
	int n,m;
	int main(){
	scanf("%d%s%d",&m,s,&n);
	root=build(s,0,strlen(s)-1);
	while(n--){
	int l,r,x;
	scanf("%d%d%d",&l,&r,&x);
	split(root,b,c,++r);
	split(b,a,b,l);
	split(root,d,e,x);
	root=merge(merge(d,b),e);
	split(root,root,f,m);
	}
	dfs(root);puts("");
	return 0;
	}

view raw reference_counting_example.cpp hosted with ❤ by GitHub

其使用了[持久化][分裂/合併式]隨機二分搜尋樹
持久化的部分會在之後介紹

[分裂/合併式] 隨機二分查找樹 [Split / Merge] Randomized Binary Search Tree

今天來講解可以做區間處理的Randomized Binary Search Tree
好比treap，可以利用拆分跟合併的方式來做區間處理
感謝伯恩大神的指導，請參考其網站

寫起來並不會比需要旋轉的難
先定義他的節點:

	struct node{
	T data;
	int s;
	//可以再加入其他維護值(max,min等等)做區間處理用
	node *l,*r;
	node(const T &d):data(d),s(1),l(0),r(0){}
	inline void up(){
	s=1;
	if(l)s+=l->s;
	if(r)s+=r->s;
	}
	inline void down(){
	//這邊是放作區間維護需要的更新(懶惰標記下推)
	//(min,max,是否反轉區間....等等)
	//本範例只提供最基本的處理
	}
	}*root;

view raw rbst_node.cpp hosted with ❤ by GitHub

可以在裡面增加一些懶惰標記的更新(min,max,rev...等等)

計算節點大小

	inline int size(node *o){
	return o?o->s:0;
	}

view raw rbst_size.cpp hosted with ❤ by GitHub

主要利用[分裂/合併]來進行區間處理
接下來講解分裂(參見 treap分裂):

	void split(node *o,node *&a,node *&b,int k){
	if(!o)a=b=0;
	else{
	o->down();
	if(k<=size(o->l)){
	b=o;
	split(o->l,a,b->l,k);
	}else{
	a=o;
	split(o->r,a->r,b,k-size(o->l)-1);
	}
	o->up();
	}
	}

view raw rbst_split.cpp hosted with ❤ by GitHub

這是將o按中序將前k個節點分到a，剩下的分到b

合併(參見 treap合併):

	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	static int x;
	if(x++%(a->s+b->s)<a->s){
	a->down();
	a->r=merge(a->r,b);
	a->up();
	return a;
	}else{
	b->down();
	b->l=merge(a,b->l);
	b->up();
	return b;
	}
	}

view raw rbst_merge.cpp hosted with ❤ by GitHub

這就是隨機的精華所在
每次merge時，a有size(a)/(size(a)+size(b))的機率將a作為root
b反之亦然
而本來random是這樣寫的:

	inline int ran(){
	static int x=20160425;
	return (x=0xdefaced*x+1)&INT_MAX;
	}

view raw rbst_ran.cpp hosted with ❤ by GitHub

但是看了丁安立魔法師的blog，發現只要x++就好了，也不知道為甚麼

如果只是要做普通的二分搜尋樹，可以利用排名來求出其在整顆樹中的名次，然後再相對應處做插入

	inline int rank(const T &data){
	//使用前必須保證整顆樹是BST
	//否則會run time error
	node *p=root;
	int cnt=0;
	while(p){
	if(data<=p->data)p=p->l;
	else cnt+=size(p->l)+1,p=p->r;
	}
	return cnt;
	}
	inline void insert(const T &data,int k){
	//在第k個位置之前插入data
	node *a,*b,*now;
	split(root,a,b,k);
	now=new node(data);
	a=merge(a,now);
	root=merge(a,b);
	}

view raw rbst_rank_insert.cpp hosted with ❤ by GitHub

插入data可以寫成:
bst.insert(data,bst.rank(data));
刪除也可以用類似的方法處理

旋轉式的randomize bst就可以做這些處理了(其實分裂合併式bst速度有點慢)，那為何還需要 分裂/合併 呢?
我們可以把整顆樹的中序走訪看成是一條陣列
-->因此可以利用它來作區間的維護

像是區間的最大最小值，區間反轉啦，區間移動、刪除等等都可以利用它在logn的時間完成
只須修改其up跟down函數就可以達成目的
凡是線段樹能做到的事情，他都能做到，可以用它來解決很複雜的區間處理問題

注意的是，在有懶惰標記的情況下，如果要詢問一個區間必須在切出那塊區間後先進行down的操作再進行詢問，否則懶惰標記可能沒有被推下去，範例如下:

	/*需要再node裡面增加tag跟ma用來儲存區間增加量跟最大值*/
	int ask(node *&o,int l,int r){
	/*在o子樹詢問區間[l,r]的最大值*/
	node *a,*b,*c;
	split(o,a,b,l-1);
	split(b,b,c,r-l+1);
	b->down();/*記得要先將懶惰標記下推*/
	int ans=b->ma;
	o=merge(a,merge(b,c));
	return ans;
	}
	int add(node *&o,int l,int r,int v){
	/*在o子樹將區間[l,r]的值都加上v*/
	node *a,*b,*c;
	split(o,a,b,l-1);
	split(b,b,c,r-l+1);
	b->tag+=v;
	o=merge(a,merge(b,c));
	}

view raw rbst_ask_add.cpp hosted with ❤ by GitHub

這個範例up()跟down()也要重寫:

	inline void up(){
	size=1;
	ma=data;
	if(l){
	s+=l->s;
	ma=max(ma,l->ma+l->tag);
	}
	if(r){
	s+=r->s;
	ma=max(ma,r->ma+r->tag);
	}
	}
	inline void down(){
	data+=tag;
	if(l)l->tag+=tag;
	if(r)r->tag+=tag;
	tag=0;
	}

view raw rbst_tag_up_down.cpp hosted with ❤ by GitHub

因為應用時分靈活，故不提供樣板，只做介紹

[ Randomized Binary Search Tree ] 隨機二分查找樹

今天來介紹隨機二分查找樹，因為看了很多外國的文章看了半天都看不懂，現在好不容易看懂英文了，就把它用中文的方式來介紹吧!
隨機二分查找樹，是利用隨機數或機率分布來達到平衡的條件，其證明以附在連結中。
利用隨機數的方法包括Treap，但是這太常見了，所以掠過。

這邊要介紹不需額外再節點紀錄隨機值的方式，透過其節點大小來計算其是否為根或是根據節點大小的比例隨機插入。

維持平衡用左旋根右旋(參見:樹旋轉):
接下來來講解一下它的插入
這裡會用到兩個函數:
insert():插入節點
insert_as_root(node *&p,T k):將k插入子樹p並做為p的根節點
為甚麼要這樣做呢?
當在對節點p進行插入時，新插入點根據隨機分布會有1/(size(p)+1)的機率成為這顆子樹的根
因此可以以遞迴處理
若此節點的值>插入值，則插入其左節點，然後右旋，反之亦然
其常數很小，所以常常插入時間比size balanced tree快，但是深度太大，刪除時間較慢
其平均深度等價於在一棵普通的BST進行隨機插入最終的平均深度，因此為2nlogn

而對於刪除節點，和Treap一樣，有兩種不同的做法:

第一種是透過與左偏樹類似的方法刪除，不需要旋轉，通常效率交高
合併左右子樹，然後刪除其根節點
合併的方式利用了隨機分布的概念
假設需將a,b合併
則有size(a)/(size(a)+size(b))的機率將b合併到a子樹
反之有size(b)/(size(a)+size(b))的機率將a合併到b子樹

第二種作法完全依賴於旋轉
在刪除時如果要被刪除的節點不是一條鏈的話，就按造隨機的概念進行旋轉
有size(左子樹)/(size(左子樹)+size(右子樹))的機率進行右旋
反之有size(右子樹)/(size(左子樹)+size(右子樹))的機率進行左旋

以下為第一種作法(效率較高):

	#ifndef RANDOMIZED_BINARY_SEARCH_TREE
	#define RANDOMIZED_BINARY_SEARCH_TREE
	template<typename T>
	class random_bst{
	private:
	struct node{
	T data;
	unsigned size;
	node *ch[2];
	node(const T &d):data(d),size(1){ch[0]=ch[1]=0;}
	inline void up(){
	size=(ch[0]?ch[0]->size:0)+(ch[1]?ch[1]->size:0)+1;
	}
	}*root;
	unsigned seed;
	inline int size(node *o){return o?o->size:0;}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->size=b->size;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->up();
	}
	inline int ran(){
	return seed=0xdefaced*seed+1;
	}
	void clear(node *&p){
	if(p)clear(p->ch[0]),clear(p->ch[1]),delete p;
	}
	void insert_as_root(node *&p,const T &data){
	if(!p)p=new node(data);
	else{
	p->size++;
	insert_as_root(p->ch[p->data<data],data);
	rotate(p,!(p->data<data));
	}
	}
	void insert(node *&p,const T &data){
	if(ran()%(size(p)+1)==0){
	insert_as_root(p,data);
	}else{
	p->size++;
	insert(p->ch[p->data<data],data);
	}
	}
	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	if(ran()%(a->size+b->size)<a->size){
	a->ch[1]=merge(a->ch[1],b);
	a->up();
	return a;
	}else{
	b->ch[0]=merge(a,b->ch[0]);
	b->up();
	return b;
	}
	}
	bool erase(node *&o,const T &data){
	if(!o)return 0;
	if(o->data==data){
	node *t=o;
	o=merge(o->ch[0],o->ch[1]);
	delete t;
	return 1;
	}else if(erase(o->ch[o->data<data],data)){
	o->size--;return 1;
	}return 0;
	}
	public:
	random_bst(unsigned x=20150112):root(0),seed(x){}
	~random_bst(){clear(root);}
	inline void clear(){clear(root),root=0;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o;)
	if(o->data<data)cnt+=size(o->ch[0])+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=size(o->ch[0]))o=o->ch[0];
	else if(k==size(o->ch[0])+1)return o->data;
	else k-=size(o->ch[0])+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return size(root);}
	};
	#endif

view raw Randomized Binary Search Tree1.cpp hosted with ❤ by GitHub

以下為第二種作法:

	#ifndef RANDOMIZED_BINARY_SEARCH_TREE
	#define RANDOMIZED_BINARY_SEARCH_TREE
	template<typename T>
	class random_bst{
	private:
	struct node{
	T data;
	unsigned s;
	node *ch[2];
	node(const T&d):data(d),s(1){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	unsigned x;
	inline unsigned ran(){
	return x=x*0xdefaced+1;
	}
	inline void rotate(node *&a,bool d){
	node *b=a;
	a=a->ch[!d];
	a->s=b->s;
	b->ch[!d]=a->ch[d];
	a->ch[d]=b;
	b->s=b->ch[0]->s+b->ch[1]->s+1;
	}
	void insert_as_root(node *&p,const T &data){
	if(!p->s){
	p=new node(data);
	p->ch[0]=p->ch[1]=nil;
	}else{
	++p->s;
	insert_as_root(p->ch[p->data<data],data);
	rotate(p,!(p->data<data));
	}
	}
	void insert(node *&p,const T &data){
	if(ran()%(p->s+1)==0){
	insert_as_root(p,data);
	}else{
	++p->s;
	insert(p->ch[p->data<data],data);
	}
	}
	bool erase(node *&o,const T &data){
	if(!o->s)return 0;
	if(o->data==data){
	if(!o->ch[0]->s||!o->ch[1]->s){
	node *t=o;
	o=o->ch[0]->s?o->ch[0]:o->ch[1];
	delete t;
	}else{
	--o->s;
	bool d=ran()%(o->ch[0]->s+o->ch[1]->s)<o->ch[0]->s;
	rotate(o,d);
	erase(o->ch[d],data);
	}
	return 1;
	}else if(erase(o->ch[o->data<data],data)){
	--o->s;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	random_bst(unsigned s=20150112):nil(new node),root(nil),x(s){}
	~random_bst(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T &data){
	insert(root,data);
	}
	inline bool erase(const T &data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	for(node *o=root;o->s;)
	if(o->data==data)return 1;
	else o=o->ch[o->data<data];
	return 0;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->s;)
	if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->s)o=o->ch[0];
	else if(k==o->ch[0]->s+1)return o->data;
	else k-=o->ch[0]->s+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->s;}
	};
	#endif

view raw Randomized Binary Search Tree2.cpp hosted with ❤ by GitHub

字典樹 Trie

今天完成了字典樹 Trie的模板，可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N)，在字串匹配上有很大的幫助(AC字動機)，但是因為每個節點都要記錄所有字元，是非常耗空間的
通常將根節點設為"沒有字元"，若是想進一步了解Trie請自行google吧!
以下為模板:

	#ifndef TRIE
	#define TRIE
	template<typename T,char L='A',char R='z'>
	class trie{
	private:
	struct node{
	node *tr[R-L+1],*pa;
	T data;
	int ref;
	bool is;
	node():ref(0),is(0){
	for(int i=0;i<=R-L;i++)tr[i]=NULL;
	}
	~node(){
	for(int i=0;i<=R-L;i++){
	if(tr[i])delete tr[i];
	}
	}
	}root;
	int _size;
	public:
	class point_iterator{
	friend trie;
	private:
	node *p;
	public:
	point_iterator(){p=NULL;}
	inline operator bool (){return p?1:0;}
	inline T &operator *(){return p->data;}
	inline void operator =(T d){p->data=d;}
	};
	inline void clear(){
	for(int i=0;i<=R-L;i++)if(root.tr[i]){
	delete root.tr[i],root.tr[i]=NULL;
	}
	}
	trie(){root.ref=0;clear();_size=0;}
	~trie(){clear();}
	inline int size(){return _size;}
	inline point_iterator find(const char *s){
	point_iterator it;
	node *now=&root;
	for(int i=0;s[i];i++){
	if(!now->tr[s[i]-L])return it;
	now=now->tr[s[i]-L];
	}
	if(now->is)it.p=now;
	return it;
	}
	inline point_iterator insert(const char *s,T data){
	point_iterator it=find(s);
	if(it){it=data;return it;}
	node *now=&root;
	_size++;
	for(int i=0;s[i];i++){
	if(!now->tr[s[i]-L]){
	now->tr[s[i]-L]=new node;
	now->tr[s[i]-L]->pa=now;
	}
	now=now->tr[s[i]-L],now->ref++;
	}
	now->data=data;now->is=1;
	it.p=now;
	return it;
	}
	inline T &operator[](const char *s){
	point_iterator it=find(s);
	if(!it)it=insert(s,T());
	return it.p->data;
	}
	inline bool erase(const char *s){
	if(!find(s))return 0;
	node *now=&root;_size--;
	for(int i=0;s[i];i++){
	if(i&&!now->ref){
	now->pa->tr[s[i-1]-L]=NULL;
	delete now;return 1;
	}
	now=now->tr[s[i]-L],now->ref--;
	}
	now->is=0;
	return 1;
	}
	};
	#endif

view raw trie.cpp hosted with ❤ by GitHub

跟stl map的用法類似
trie<int >t;  //定義一個存int的Trie
trie<int ,'a','z'>t  //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it;  //定義一個節點迭代器
t.insert("asd",1);  //插入1到"asd"的位置(若原來已有值則覆蓋)，傳回插入節點的point_iterator
t.find("asd");  //傳回"asd"位置的point_iterator，若無資料point_iterator為NULL，請注意
t["asf"];  //若"asd"存在資料，傳回其引用位置，若不存在則插入並傳回其引用位置
t.erase("asd");  //刪除"asd"節點，若成功刪除則傳回true，失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear();  //清空trie

[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 ) 複雜度證明(論文)

找了好久終於找到中国广东中山纪念中学的陈启峰size balanced tree的原作論文中文翻譯版
若需參考要者請點擊下載
原文連結

重量左偏樹 weight-biased leftist tree

之前提到的左偏樹是深度左偏樹，雖然複雜度也是logn，但是重量左偏樹的速度在實作上是明顯較深度左偏樹快的
若是想了解深度左偏樹 height-biased leftist tree 或是左偏樹的理論請參考這篇文章
以下提供模板(使用方法與深度左偏樹相同):

	#include<functional>
	#ifndef WEIGHT_BIASED_LEFTIST_TREE
	#define WEIGHT_BIASED_LEFTIST_TREE
	template<typename T,typename _Compare=std::less<T> >
	class wb_leftist_tree{
	private:
	struct node{
	T data;
	int size;
	node *l,*r;
	node(const T&d):data(d),size(1),l(0),r(0){}
	}*root;
	_Compare cmp;
	inline int size(node *o){return o?o->size:0;}
	node *merge(node *a,node *b){
	if(!a||!b)return a?a:b;
	if(cmp(a->data,b->data)){
	node *t=a;a=b;b=t;
	}
	a->r=merge(a->r,b);
	if(size(a->l)<size(a->r)){
	node *t=a->l;a->l=a->r;a->r=t;
	}
	a->size=size(a->l)+size(a->r)+1;
	return a;
	}
	void _clear(node *&o){
	if(o)_clear(o->l),_clear(o->r),delete o;
	}
	public:
	wb_leftist_tree():root(0){}
	~wb_leftist_tree(){_clear(root);}
	inline void clear(){
	_clear(root),root=0;
	}
	inline void join(wb_leftist_tree &o){
	root=merge(root,o.root);
	o.root=0;
	}
	inline void swap(wb_leftist_tree &o){
	node *t=root;
	root=o.root;
	o.root=t;
	}
	inline void push(const T&data){
	root=merge(root,new node(data));
	}
	inline void pop(){
	if(!root)return;
	node *tmd=merge(root->l,root->r);
	delete root;
	root=tmd;
	}
	inline const T& top(){return root->data;}
	inline int size(){return size(root);}
	inline bool empty(){return !size(root);}
	};
	#endif

view raw weight_biased_leftist_tree.cpp hosted with ❤ by GitHub

在函式中傳入使用者自定函式的方法(C++ Functor 仿函式)

一般來說在函式中傳入使用者自定函式通常會用函數指標
但是C++ template提供了一個較為便利的函數參數，以物件的方式傳入
可支援一般函數或利用重載()運算子所定義的物件
詳情請看代碼:

	#include<stdio.h>
	template<typename T,typename _Compare>
	T min_element(T first,T last,_Compare cmp){
	//這種做法可以將函式當成物件傳入
	T ans=first;
	while(++first!=last){
	if(cmp(*first,*ans))ans=first;
	}
	return ans;
	}
	//盡量使用const避免出錯，一般STL的傳入函式也請這樣使用
	bool const cmp(const int &a,const int &b){
	return a<b;
	}
	struct _cmp{
	bool operator ()(const int &a,const int &b)const{
	return a>b;
	}
	};
	template<typename T>
	struct __cmp{
	bool operator ()(const T &a,const T &b)const{
	return a<b;
	}
	};
	int s[20]={1,5,6,-91,2,8,4,5,-5,-9,-4,-1,5,8,6,3,7,-9};
	//max:8 min:-91
	int main(){
	_cmp my_cmp;//創立一個比較物件
	printf("%d\n",*min_element(s,s+18,my_cmp));//8
	printf("%d\n",*min_element(s,s+18,cmp));//-91
	printf("%d\n",*min_element(s,s+18,_cmp()));//8
	printf("%d\n",*min_element(s,s+18,__cmp<int >()));//-91
	return 0;
	}

view raw Functor.cpp hosted with ❤ by GitHub

歐拉函數 乘法模逆元

今天來講一下歐拉函數及乘法模逆元
首先是歐拉函數
定義: 歐拉函數$φ(N)$是小于或等于$N$的正整數中與$N$互質的數的個數$(N>0)$
其值為
$φ(N)=N \times (1-1/P_1) \times (1-1/P_2) \times (1-1/P_3) \times ... \times (1-1/P_k)$
其中$P_i$為$N$的質因數，總共有$k個$

因此可以利用質數篩法在線性或趨近線性的時間內完成某一區間的歐拉函數:

	#define maxn 10000000
	int euler[maxn+5];
	bool is_prime[maxn+5];
	inline void init_euler(){
	is_prime[1]=1;//一不是質數
	for(int i=1;i<=maxn;i++)euler[i]=i;
	for(int i=2;i<=maxn;i++){
	if(!is_prime[i]){//是質數
	euler[i]--;
	for(int j=i<<1;j<=maxn;j+=i){
	is_prime[j]=1;
	euler[j]=euler[j]/i*(i-1);
	}
	}
	}
	}

view raw range phi.cpp hosted with ❤ by GitHub

計算單一數的歐拉函數值可利用平方根質數法求:

	inline int Euler(int n){
	int ans=n;
	for(int i=2;i*i<=n;i++){
	if(n%i==0){
	ans=ans/i*(i-1);
	while(n%i==0)n/=i;
	}
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
	}

view raw phi.cpp hosted with ❤ by GitHub

接下來介紹乘法模逆元
一整數$A$對同餘$B$之乘法模逆元是指滿足以下公式的整數$R$ $$A^{-1}≡R \; (mod \; B)$$
也可以寫成 $$AR≡1 \; (mod \; B)$$
根據歐拉定理: 當$gcd(A,B)=1$，$A^{φ(B)} ≡ 1 \; mod \;B$
(若$B$是質數，則$φ(B)=B-1$，競賽題目$B$大多為質數，不需求歐拉函數)
為了方便，我們定義 $X\%Y$ 表示$X$除以$Y$的餘數
顯然 $R=A^{φ(B)-1} \;\% \; B$ 是$A$的模$B$乘法模逆元，可以由次方快速冪再$\ord{logn}$的時間得到:

	inline long long pow_mod(int a,int b){//條件:gcd(a,b)=1
	long long mod=b,tmd=a,ans=1;
	for(b=Euler(b)-1;b;b>>=1){
	if(b&1)ans=ans*tmd%mod;
	tmd=tmd*tmd%mod;
	}
	return ans;
	}

view raw mod inverse.cpp hosted with ❤ by GitHub

另一種模逆元的解法:
計算$A$的模$B$乘法模逆元，可由擴展歐幾里得演算法得到
設$exgcd$擴展歐幾里得演算法的函數，它接受兩個整數$A,B$，輸出三個整數$g,x,y$。
$g,x,y$滿足等式$A \times x+B \times y=g$，且$g=gcd(A,B)$。
當$B=0$時，有$x=1,\; y=0$使等式成立
當$B>0$，在歐基里德算法的基礎上，已知 $$gcd(A,B)=gcd(B,A\%B)$$
先遞迴求出$x^{'},y^{'}$滿足 $$Bx^{'}+(A\%B)y^{'}=gcd(B,A\%B)=gcd(A,B)$$
然後可以將上面的式子化簡得 $$Bx^{'}+(A-(A/B) \times B)y^{'}=gcd(A,B)$$ $$Ay^{'}+Bx^{'}-(A/B) \times By^{'}=gcd(A,B)$$
這裡的除法是整除法，會自動無條件捨去。把含$B$的因式提取一個$B$，可得 $$Ay^{'}+B(x^{'}-(A/B) \times y^{'})=gcd(A,B)$$
故$x=y^{'},\; y=x^{'}-(A/B) \times y^{'}$

若$g=1$，則$A$的模$B$乘法模逆元為$B+x$
$(A \times x+B \times y)\%B=1 \longrightarrow B \times y是B的倍數 \longrightarrow A(x+B)\%B=1 \; (因為x可能小於0)$
總複雜度和歐基里德算法相同，皆為$\ord{logn}$

擴展歐幾里得演算法函數實做:

	template<typename T>
	T exgcd(T a,T b,T &x,T &y){//a*x+b*y=(return)
	if(b){
	T tmd=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return tmd;
	}
	x=1,y=0;
	return a;
	}

view raw exgcd.cpp hosted with ❤ by GitHub

[ size balanced tree ] 節點大小平衡樹 ( 傻B樹 )

它是由中国广东中山纪念中学的陈启峰發明的[已新增其中文論文連結]
跟一般的平衡樹一樣，靠左旋和右旋維持其平衡
他的精華來自於maintain函數
聽說是均攤$\ord 1$的，傳說中速度僅次於紅黑樹
coding複雜度跟Treap差不多，比AVL Tree好寫
平衡調件為: 每顆子樹的大小不小於其兄弟子樹的大小
我只提供模板，這裡有詳細的介紹

	#ifndef SIZE_BALANCED_TREE
	#define SIZE_BALANCED_TREE
	template<typename T>
	class sb_tree{
	private:
	struct node{
	node *ch[2];
	int s;
	T data;
	node(const T&d):s(1),data(d){}
	node():s(0){ch[0]=ch[1]=this;}
	}*nil,*root;
	inline void rotate(node *&a,bool d){
	node *b=a->ch[!d];
	a->ch[!d]=b->ch[d];
	b->ch[d]=a;
	b->s=a->s;
	a->s=a->ch[0]->s+a->ch[1]->s+1;
	a=b;
	}
	void maintain(node *&o,bool d){
	if(o->ch[d]->ch[d]->s>o->ch[!d]->s){
	rotate(o,!d);
	}else if(o->ch[d]->ch[!d]->s>o->ch[!d]->s){
	rotate(o->ch[d],d);
	rotate(o,!d);
	}else return;
	maintain(o->ch[1],1);
	maintain(o->ch[0],0);
	maintain(o,1);
	maintain(o,0);
	}
	void insert(node *&o,const T&data){
	if(!o->s){
	o=new node(data);
	o->ch[0]=o->ch[1]=nil;
	}else{
	++o->s;
	bool d=o->data<data;
	insert(o->ch[d],data);
	maintain(o,d);
	}
	}
	inline void success_erase(node *&o){
	node *t=o;
	o=o->ch[0]->s?o->ch[0]:o->ch[1];
	delete t;
	}
	bool erase(node *&o,const T&data){
	if(!o->s)return 0;
	if(o->data==data){
	if(!o->ch[0]->s||!o->ch[1]->s)success_erase(o);
	else{
	--o->s;
	node **t=&o->ch[1];
	for(;(*t)->ch[0]->s;t=&(*t)->ch[0])(*t)->s--;
	o->data=(*t)->data;
	success_erase(*t);
	}return 1;
	}else if(erase(o->ch[o->data<data],data)){
	--o->s;return 1;
	}else return 0;
	}
	void clear(node *&o){
	if(o->s)clear(o->ch[0]),clear(o->ch[1]),delete o;
	}
	public:
	sb_tree():nil(new node),root(nil){}
	~sb_tree(){clear(root),delete nil;}
	inline void clear(){clear(root),root=nil;}
	inline void insert(const T&data){
	insert(root,data);
	}
	inline bool erase(const T&data){
	return erase(root,data);
	}
	inline bool find(const T&data){
	node *o=root;
	while(o->s&&o->data!=data)o=o->ch[o->data<data];
	return o->s;
	}
	inline int rank(const T&data){
	int cnt=0;
	for(node *o=root;o->s;)
	if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
	else o=o->ch[0];
	return cnt;
	}
	inline const T&kth(int k){
	for(node *o=root;;)
	if(k<=o->ch[0]->s)o=o->ch[0];
	else if(k==o->ch[0]->s+1)return o->data;
	else k-=o->ch[0]->s+1,o=o->ch[1];
	}
	inline const T&operator[](int k){
	return kth(k);
	}
	inline const T&preorder(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(x->data<data)y=x,x=x->ch[1];
	else x=x->ch[0];
	if(y)return y->data;
	return data;
	}
	inline const T&successor(const T&data){
	node *x=root,*y=0;
	while(x->s)
	if(data<x->data)y=x,x=x->ch[0];
	else x=x->ch[1];
	if(y)return y->data;
	return data;
	}
	inline int size(){return root->s;}
	};
	#endif

view raw size balanced tree.cpp hosted with ❤ by GitHub

因為自己寫的速度有點慢，可以參考這邊一些大神寫的code