数据结构：ST表

BZOJ1699

在经历了树套树和主席树的洗礼之后，所有的数据结构都显得格外地亲切，和自然。。

ST算法能够实现O（nlogn）的预处理的情况下完成O（1）的区间最值查询

虽然这要求区间是静态的，也就是我们不能对区间进行修改

如果是动态的，区间最值问题，线段树或者分块儿

另外RMQ问题和LCA可以相互转化，我们回头单独介绍

这里先给出预处理：

（如果使用标准RMQ算法，可以完成O（n）的预处理，还有约束RMQ一类的问题）

void pre()
{
    for(int i=1;i<=n;i++)
        mx[i][0]=mn[i][0]=a[i];
    int t=log(n)/log(2);
    for(int i=1;i<=t;i++)
    for(int j=n;j>0;j--)
    {
        mx[j][i]=mx[j][i-1];
        if(j+(1<<(i-1))<=n)
            mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
    }
    for(int i=1;i<=t;i++)
    for(int j=n;j>0;j--)
    {
        mn[j][i]=mn[j][i-1];
        if(j+(1<<(i-1))<=n)
            mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
    }
}

其实预处理就是一个递推式

然后是查询：

int rmq(int l,int r)
{
    int m=log(r-l+1)/log(2);
    int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
    int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
    return a-b;
}

最后给出完整的，实现。。。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=50005;
 6 int n,q;
 7 int a[maxn],mn[maxn][16],mx[maxn][16];
 8 void pre()
 9 {
10     for(int i=1;i<=n;i++)
11         mx[i][0]=mn[i][0]=a[i];
12     int t=log(n)/log(2);
13     for(int i=1;i<=t;i++)
14     for(int j=n;j>0;j--)
15     {
16         mx[j][i]=mx[j][i-1];
17         if(j+(1<<(i-1))<=n)
18             mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
19     }
20     for(int i=1;i<=t;i++)
21     for(int j=n;j>0;j--)
22     {
23         mn[j][i]=mn[j][i-1];
24         if(j+(1<<(i-1))<=n)
25             mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
26     }
27 }
28 int rmq(int l,int r)
29 {
30     int m=log(r-l+1)/log(2);
31     int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
32     int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
33     return a-b;
34 }
35 int main()
36 {
37     scanf("%d%d",&n,&q);
38     for(int i=1;i<=n;i++)
39         scanf("%d",&a[i]);
40     pre();
41     int x,y;
42     while(q--)
43     {
44         scanf("%d%d",&x,&y);
45         printf("%d
",rmq(x,y));
46     }
47     return 0;
48 }

像这种成型的算法，实在理解不了就背下来，不过要先会推导否则死翘翘，硬背是会凉的。