[ sparse table ] RMQ問題的稀疏表算法

RMQ問題(Range Minimum/Maximum Query,區間最值問題)，通常是給定一條串列s，有若干次的詢問查詢區間L至區間R的最大(小)值。
相信關於RMQ問題使用線段樹的做法很多人都有一定的了解，這邊提供另外一種在線不可修改的做法，稱為稀疏表算法，其預處理時間為$\ord{NlogN}$，N為串列長度，
查詢時間為$\ord 1$，是一種高效的演算法。

關於此算法的說明請看http://noalgo.info/489.html
由連結提供的程式碼效能是十分差的，因此這邊提供我的模板(以區間最小值為例):

	#define MAXN 100000
	#define MAX_LOG 17
	int n,s[MAXN+5];
	int st[MAX_LOG+1][MAXN+5];
	inline void init(){/*假設區間由[0~n-1]*/
	for(int i=0;i<n;++i)st[0][i]=s[i];
	for(int j=1;(1<<j)<=n;++j)
	for(int i=0;i+(1<<j)<=n;++i)
	st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
	}
	inline int RMQ(int a,int b){/*用<algorithm>內建函式求log*/
	int k=std::__lg(b-a+1);
	return min(st[k][a],st[k][b-(1<<k)+1]);
	}

view raw Sparse Table.cpp hosted with ❤ by GitHub

[ Palindromic Tree ] 回文樹(回文自動機)

回文樹是去年新出的資料結構，由一個俄羅斯codeforces的紅人Mikhail Rubinchik在2014年發明的(http://codeforces.com/blog/entry/13959)，雖然名子直接翻譯叫回文樹，但他長的比較像一個自動機，所以也有很多人翻回文自動機。
在構造它之前，我們必須先證明一個長度n的字串其不同的回文子字串個數<=n，什麼是不同的回文子字串?就是長的不同的回文子字串，及把出現位置不同但形狀一樣的回文子字串當做是同樣的子字串。

證明:

1. 由左往右一個一個增加字符，則新產生的回文子字串其結尾一定是當前增加的字符x
2. 考慮以當前位置為結尾的最長回文x......x，顯而易見的，若產生除了x......x之外其它的回文子串，則必定被x......x所包含
3. 若增加字符x後，產生了除了x......x之外其它的回文子串，則根據回文的性質，其一定早已在x......的部分理出現(例:假設S是對稱點x...S.xax，因為回文的性質所以S的另一邊也會出現相同的字串xax.S.xax)
4. 因此每增加一個字符最多只會產生一個新的回文子字串，而長度為n的字符串最多只會產生n種不同的回文子字串

接下來進行回文自動機元素的詳細解說:

回文自動機包含以下元素:

1. 狀態St，所有節點的集合，一開始兩個節點，0表示偶數長度串的根和1表示奇數長度串的根
2. last 新增加一個字符後所形成的最長回文串的節點編號
3. s 當前的字符串(一開始設s[0]=-1(可以是任意一個在串S中不會出現的字符))
4. n 表示添加的字符個數

每個節點代表一個不同的回文子字串，我們在每個節點會儲存一些數值:

1. len 表示所代表的回文子字串長度
2. next[c] 表示所代表的回文子字串在頭尾各增加一個字符c後的回文字串其節點編號
3. fail 表示所代表的回文子字串不包括本身的最長後綴回文子串的節點編號
4. cnt(非必要) 表示所代表的回文子字串在整體字串出現的次數(在建構完成後呼叫count()才能計算)
5. num(非必要) 表示所代表的回文子字串其後綴為回文字串的個數

注意一開始必須先將狀態初始化St[0].len=0，St[1].len=-1，last=0，s[0]=-1，n=0

關於構造方法及圖片說明請參考:http://blog.csdn.net/u013368721/article/details/42100363
概念請參考:http://blog.csdn.net/MaticsL/article/details/43651169
證明請參考:http://yqcmmd.com/index.php/2015/03/30/746/

最後提供模板(使用STL vector)，因為St的元素在解題的過程中常會被用到所以就不封裝了:

	#ifndef PALINDROMIC_TREE
	#define PALINDROMIC_TREE
	#include<vector>
	struct palindromic_tree{
	struct node{
	int next[26],fail,len;/*這些是必要的元素*/
	int cnt,num;/*這些是額外維護的元素*/
	node(int l=0):fail(0),len(l),cnt(0),num(0){
	for(int i=0;i<26;++i)next[i]=0;
	}
	};
	std::vector<node >St;
	std::vector<char >s;
	int last,n;
	palindromic_tree():St(2),last(1),n(0){
	St[0].fail=1;
	St[1].len=-1;
	s.push_back(-1);
	}
	inline void clear(){
	St.clear();
	s.clear();
	last=1;
	n=0;
	St.push_back(0);
	St.push_back(-1);
	St[0].fail=1;
	s.push_back(-1);
	}
	inline int get_fail(int x){
	while(s[n-St[x].len-1]!=s[n])x=St[x].fail;
	return x;
	}
	inline void add(int c){
	s.push_back(c-='a');
	++n;
	int cur=get_fail(last);
	if(!St[cur].next[c]){
	int now=St.size();
	St.push_back(St[cur].len+2);
	St[now].fail=St[get_fail(St[cur].fail)].next[c];
	/*不用擔心會找到空節點，由證明的過程可知*/
	St[cur].next[c]=now;
	St[now].num=St[St[now].fail].num+1;
	}
	last=St[cur].next[c];
	++St[last].cnt;
	}
	inline void count(){/*cnt必須要在構造完後呼叫count()去計算*/
	std::vector<node>::reverse_iterator i=St.rbegin();
	for(;i!=St.rend();++i){
	St[i->fail].cnt+=i->cnt;
	}
	}
	inline int size(){/*傳回其不同的回文子串個數*/
	return St.size()-2;
	}
	};
	#endif

view raw Palindromic Tree.cpp hosted with ❤ by GitHub

[ Heavy-Light Decomposition ] 樹鏈剖分模板+LCA

在某些狀況下，我們希望對樹上a點到b點的路徑進行修改或查詢的動作，而且這些動作用一般的樹壓平RMQ或是離線處理無法完成的，這個時候我們可以利用特殊的方法將樹拆成長鏈。
長鏈可以搭配良好的資料結構。只要找出樹上所有長鏈，每條長鏈套用線段樹、BIT、Sparse Table、BST、Heap，就能降低時間複雜度。

可以利用簡單的做法將dfs序切成許多長鏈:

1. 首先先設定其中一點為根，算出每個子樹有多少節點
2. 樹上每個節點各自連向最大的子樹，相連的部分會自然形成鏈

通常步驟二會進行一次dfs，每次朝著最大的子樹走，每個節點記錄其時間戳記及所在的鏈(通常是記鏈首)，這樣就可以將樹壓平的結果切成許多鏈，使得樹鏈剖分同時可以做到樹壓平的操作。

我們可以進行一個簡單的證明:

• 假設節點數為V，由根往任意葉節點走，一旦遇到新鏈，新鏈的子樹必小於等於原鏈子樹，剩下的節點數量不到一半，所以沿途最多遇到 logV 條鏈。

因為一條路徑藉由 LCA 拆成兩段，沿途最多遇到 2*logV 條鏈，所以在任意兩點a,b間最多只需要進行2*logV次的區間操作，若是套線段樹之類的結構可以做到$\ord{log^2V}$
這些操作都可以在求LCA的過程中完成:

	#include<vector>
	#define MAXN 100005
	typedef std::vector<int >::iterator VIT;
	int siz[MAXN],max_son[MAXN],pa[MAXN],dep[MAXN];
	/*節點大小、節點大小最大的孩子、父母節點、深度*/
	int link_top[MAXN],link[MAXN],cnt;
	/*每個點所在鏈的鏈頭、樹鏈剖分的DFS序、時間戳*/
	std::vector<int >G[MAXN];/*用vector存樹*/
	void find_max_son(int x){
	siz[x]=1;
	max_son[x]=-1;
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==pa[x])continue;
	pa[*i]=x;
	dep[*i]=dep[x]+1;
	find_max_son(*i);
	if(max_son[x]==-1||siz[*i]>siz[max_son[x]])max_son[x]=*i;
	siz[x]+=siz[*i];
	}
	}
	void build_link(int x,int top){
	link[x]=++cnt;/*記錄x點的時間戳*/
	link_top[x]=top;
	if(max_son[x]==-1)return;
	build_link(max_son[x],top);/*優先走訪最大孩子*/
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==max_son[x]||*i==pa[x])continue;
	build_link(*i,*i);
	}
	}
	inline int find_lca(int a,int b){
	/*求LCA，可以在過程中對區間進行處理*/
	int ta=link_top[a],tb=link_top[b];
	while(ta!=tb){
	if(dep[ta]<dep[tb]){
	std::swap(ta,tb);
	std::swap(a,b);
	}
	//這裡可以對a所在的鏈做區間處理
	//區間為(link[ta],link[a])
	ta=link_top[a=pa[ta]];
	}
	/*最後a,b會在同一條鏈，若a!=b還要在進行一次區間處理*/
	return dep[a]<dep[b]?a:b;
	}

view raw Heavy-Light Decomposition.cpp hosted with ❤ by GitHub

若樹鏈剖分的目的只是為了求LCA，build_link()及find_lca()有更好的做法:

	inline void build_link(int root,int n){
	pa[root]=-1;
	for(int i=1;i<=n;++i){/*假設節點編號是1~n*/
	if(~pa[i]&&max_son[pa[i]]==i)continue;
	for(int j=i;j!=-1;j=max_son[j])link_top[j]=i;
	}
	}
	inline int find_lca(int a,int b){
	while(link_top[a]!=link_top[b]){
	if(dep[link_top[a]]>dep[link_top[b]])a=pa[link_top[a]];
	else b=pa[link_top[b]];
	}
	return dep[a]<dep[b]?a:b;
	}

view raw Heavy-Light Decomposition LCA.cpp hosted with ❤ by GitHub

這就只需進行一次DFS

[ Suffix Array Longest Common Prefix (LCP) ] 後綴數組之最長共同前綴(高度數組)

不解釋了，可以在$\ord N$時間內得到，N是字串長度
以下提供模板:

	/*
	h:高度數組
	sa:後綴數組
	rank:排名
	*/
	inline void suffix_array_lcp(const char *s,int len,int *h,int *sa,int *rank){
	for(int i=0;i<len;++i)rank[sa[i]]=i;
	for(int i=0,k=0;i<len;++i){
	if(rank[i]==0)continue;
	if(k)--k;
	while(s[i+k]==s[sa[rank[i]-1]+k])++k;
	h[rank[i]]=k;
	}
	h[0]=0;
	}

view raw LCP.cpp hosted with ❤ by GitHub