ST表是一个可以在O(n\log n)建立，O(1) 查询区间最值的东西。
我们定义st[i][j]表示a_i ~ a_{i+2^j-1}中的最大值
我们可以很容易的写出递推式：
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
在查询的时候呢？
设查询区间为[l,r]
我们可以预处理一个log_i表示\log i的值
递推式:
log[i]=log[i/2]+1
定义x=log[r-l+1]
然后，我们就在st[l][x]和st[l-2^x+1][x]查询最大值即可
code：
int st[10101001][30],log[10101001];
log[1]=0;
for(int i=2;i<=n;i++) st[i][0]=a[i],log[i]=log[i/2]+1;
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
int query(int l,int r){
int x=log[r-l+1];
return max(st[l][x],st[l-(1<<x)+1][x]);
}
