ST表

给一个数列，巨多次询问区间最值，窝萌用ST表解决多次查询不修改问题。这篇以左闭右闭区间为例。

st [ i ] [ j ] 表示从第 i 位开始 ( 包括第 i 位 ) ，2 ^ j 个数中的最值。

显然，st [ i ] [ 0 ] = n [ i ]         st [ i ] [ j ] = max ( st [ i ] [ j - 1 ] , st [ i + 2^( j - 1) ] [ j - 1 ] ) 

在预处理时，由于需要用到st [ i + 2^( j - 1) ] [ j - 1 ]，必须把 j 作为外层循环，否则st [ i + 2^( j - 1) ] [ j - 1 ]全是0。

预处理好了之后，窝萌就可以 O ( 1 ) 地查询区间最值 (rmq) 了。

我们发现这样一个性质 : max ( L ~ R )  =  max ( max( L ~ i ) , max( j ~ R ) )  ( L ≤ j ≤ i ≤ R )

利用窝萌预处理好的st表，取 m = log2 ( R - L + 1 )，易知max ( L ~ R )  =  max ( st [ L ] [ m ]  , st [ R - 2^m + 1] [ m ] ) （开篇说明是左闭右闭区间，其他情况注意边界+1-1即可）

#include
#include
#include
using namespace std;
int n[100005];
int a;
int st[100005][25];            //st[i][j]表示从第 i项开始(包含第 i项)，2^j 项中的最值 

void init()
{
    for(int i=1;i<=a;i++)
        st[i][0]=n[i];
    for(int j=1;j<=20;j++)                 //一定是表示 2^j 的循环在外层
                                            //1e5 ~ 2^17    1e6 ~ 2^20 
        for(int i=1;i+(1<1<=a;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void find(int ll,int rr)
{
    int mid=log2(rr-ll+1);
    int ans=max(st[ll][mid],st[rr-(1<1][mid]);
    printf("%d\n",ans);
}
int main()
{
    int m;
    scanf("%d%d",&a,&m);
    for(int i=1;i<=a;i++) scanf("%d",&n[i]);
    init();
    int l,r;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        find(l,r);
    }
    return 0;
}