[ 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