前叙
一开始我一直以为这算法叫RMQ，现在才发现这问题叫RMQ，算法是ST表
RMQ-ST表
先给出练手题的地址：LuoguP3865
sti,j
表示以第
i
个数为首的一共2j个数的最大值
gi
表示原数列
可以得到：
sti,j={gimax{sti,j−1,sti+2j−1,j−1}j=1j≠1
代码如下
int n,t,l,r,o,st[
100010][
20];
int main()
{
n=read();
t=read();
fr(i,
1,n)
st[i][
0]=read();
fr(i,
1,log2(n))
fr(j,
1,n-(
1<<i)+
1)
st[j][i]=max(st[j][i-
1],st[j+(
1<<(i-
1))][i-
1]);
while(t--)
{
l=read();
r=read();
o=log2(r-l+
1);
printf(
"%d\n",max(st[l][o],st[r-(
1<<o)+
1][o]));
}
return 0;
}
