st表

• 需求：输入一个序列\(A[n]\)?，进行\(q\)次查询，每次查询求\([l,r]\)区间的最大值。

• 问题：暴力的求法是，每次都遍历一下，求最大值，显然这个非常慢。所以我们需要引入一个高效的数据结构。

• 介绍：st表根据倍增思想实现的数据结构，主要用来求解RMQ问题，\(O(1)\)?的时间复杂度求出某个区间的最大值，最小值。

算法介绍

预处理

? 首先，我们设\(STMax[i][j]\)?：从\(i\)?开始的区间长度为\(2^j\)?的最大值，即区间范围为\([i,2^j-1]\)??。

那么很显然，对于原数组\(A[]\)，我们有\(A[i]=STMax[i][0]\)?。我们直接读入即可。（不用再建立\(A[]\)数组）

    for(int i=1;i<=n;i++){
        scanf("%d",&st[i][0]);
    }

我们如何去维护好\(STMax[i][j]\)?呢，很简单，根据\(max\)?最大值的一个性质，\(max(1,2,3,4)=max(max(1,2),max(3,4))\)?。是不是看到公式就头晕，让我们来举个例子。

假设已知区间\([1,2][3,4]\)的最大值分别为\(a,b\)，我们要求\([1,4]\)的最大值，只需要求\(max(a,b)\)。

好，我们继续深入，如果要求\([1,8]\)的最大值，我们只需要求出\([1,4],[5,8]\)??的最大值，然后在他们之中再取最大值即可。一直递增，我们可以求出更多的最大值，这个便是区间动态规划。

所以我们可以维护好区间长度，不断递推出更多的区间长度。（看不懂没关系，看下文分析）

我们上文说到，我们对所有\(STMax[i][0]\)???进行赋值，他们的区间长度都是1，最大值都是原数据\(A[i]\)????本身。那么我们是不是得到了所有长度为1的区间的最大值？，因此我们可以去求长度为2的区间的最大值。

接下来我来分析前三步。

• 求长度区间为2的最大值

根据\(max(max([1])，max([2]))\)我们可以得到\([1,2]\)这个长度为2的区间的最大值，同样的，我们能得到\([2,3],[3,4][4,5]...[N-1,N]\)所有长度为2的区间的最大值。

• 求长度区间为4的最大值

根据上面举的例子，求出\([1,4],[2,5],[3,6]....\)?所有长度区间为4的

• 求长度区间为8的最大值

求出所有长度区间为8，的最大值

...............................................

我们每一步都可以在上一步的基础上得到更大的区间。区间长度不断翻倍增长(不断乘2)，回到我们上面的定义：我们设\(STMax[i][j]\)?：从\(i\)?开始的区间长度为\(2^j\)?的最大值，所以我们在声明数组的大小的时候，第二维的最大值为整个区间的长度的对数。一般我都设置为21（大概\(2^{21}=2e6\)??）

• 声明ST表

int STMax[N][21];

• 维护ST表的代码如下

仔细看代码，别看到符号就觉得难。\((1<代表的是\(2^j\)

    for(int j=1;j<=log(n);j++){//j代表的是区间长度，n代表原数组的长度，区间长度要<=log(n),原因查看j的实际含义。
        for(int i=1;i+(1<

int query(int l,int r ){
    int k=log(r-l+1);
    return max(STMax[l][k],STMax[r-(1<

    for(int i=2;i

#include
using namespace std;
typedef long long ll;
const int N=1e5+5;
int STMax[N][23];
int lg[N];
int query(int l,int r ){
    int k=lg[r-l+1];
    return max(STMax[l][k],STMax[r-(1<