ST表预处理时的数组证明

ST表预处理时的数组证明

$a_i=x(2^x\le i<2^{x+1})$

递推方程：$a_i=a_{\frac{i}{2}}+1$

证明：

$a_{\frac{i}{2}}=x$

$2^x\le \frac{i}{2}<2^{x+1}$

$\therefore 2^{x+1}\le i<2^{x+2}$

$2\times \frac{i}{2}\le i\le 2^{x+2}$

证毕。

因此可以$O(n)$ 预处理对数数组。

然后$O(1)$ 实现区间查询。

附一个RMQ。

#define il inline
struct RMQ{
    
	int f[N][20],b[N];//pay attention init f[i][0]
	il void init(int n){
    
		for(int i=2;i<=n;i++)	//pre deal with 
			b[i]=b[i>>1]+1;    //注意从2开始
		for(int j=1;j<=b[n];j++)
			for(int i=1;i+(1<<j)-1<=n;i++)
				f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
	}
	il int que(int l,int r){
    
		int x=b[r-l+1];
		return max(f[l][x],f[r-(1<<x)+1][x]);
	}
}rm;