Sparse Table

Sparse Table.cpp

#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]);
}