RMQ(Range Minimum Query 区间最小值问题)

ST(Sparse_Table)算法

令f[i][j]表示从i开始的，长度为2^j的一段元素中的最小值

f[i][j]=min(f[i][j-1],f[i+2^(j-1)][j-1])

时间复杂度:O(nlogn)

令k为满足2^k<=r-l+1的最大整数，以l为头，r为尾两个长度为2^k的区间合起来即覆盖了[l,r]的区间

min(f[l][k],f[r-2^k+1][k])

ST表：

void ST(){
  for(int j=1;j<=log[n];j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			f[i][j]=min/max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
}

查询：

int answer(int l,int r){
	int k=a[r-l+1];
	return min(f[l][k],f[r-(1<<k)+1][k]);
}