st表

作用

找到一段区间的最值（不支持修改）

方法

f[i][j]表示从下标i为起点长度为 $2^j$ 的区间的最值

右端点就是 $i+2^j-1$

更新方式就是将区间分成两半，取两半的最值

左边区间就是[i,i+2^{(j-1)-1]，右边区间就是[i+2}(j-1),i+2^j-1]
所以写成转移方程就是f[i][j]=max(f[i][j-1],f[i+2^(j-1),j-1])

初始化

枚举长度j(表示2的j次幂)，再枚举起点i，当j=0的时候，长度就只有1，那么第i个数本身就是最值；当j！=0的时候，状态转移方程就是f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);

void init(){
	for(int j=0;j<=19;j++){
		for(int i=1;i<=n;i++){
			if(j==0)f[i][j]=a[i];
			else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}

查找区间最值

例子：
给定一个区间lr找最大值
算出长度：len=r-l+1
找出小于等于len的最大的一个2的次幂数k
那么一个以i为左端点长度为 $2^k$ 的区间和一个以j为右端点长度为 $2^k$ 的区间一定可以覆盖住这段区间
那么我们就取这两个区间的最大值就可以了
f[l][r]=max(f[l][k],f[r-2^k +1][k])

int len=r-l+1;
int k=log2(len);
ans=max(f[l][k],f[r-(1<<k)+1][k]);