Array proof during st table preprocessing

ST Array proof during table preprocessing

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

Recurrence equation ：$a_i=a_{\frac{i}{2}}+1$

prove ：

$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}$

Certificate completion .

So you can $O(n)$ Preprocessing logarithmic array .

then $O(1)$ Realize interval query .

Attached with one 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;    // Attention from 2 Start 
		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;