ST表_牛客博客

ST表

什么是ST表

ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到 $O (n \log n)$ 的预处理， $O(1)$ 的单次查询。

实现方法：

ST表分为预处理和区间查询两个部分，实现起来十分简单。

预处理的预处理：

由于我们需要每次倍增的运算，所以一定会涉及到多次计算 $2^i$ 和 $\log i$ ，所以可以对这两个数组进行预处理。
实现方案十分简单，就直接放代码了

num[0] = 1,lg[0] = -1;
for(int i = 1 ; i <= 30 ; i++)
    num[i] = num[i - 1] * 2;
for(int i = 1 ; i <= n ; i++)
    lg[i] = lg[i / 2] + 1;

真正的预处理：

设 $f[i][j]$ 表示从第i号节点到第 $i+2^j-1$ 号节点的最大值，即从 $i$ 号节点开始往后数共 $2^j$ 个节点中的最大值。
例如 $f[i][1]$ 指的就是第 $i$ 号节点和第 $i+1$ 号节点的最大值。
但是暴力的来构造肯定是不行的呀，我们考虑利用性质进行二分。我们可以逐层循环j和i，当我们循环到要处理f[i][j]时，我们其实就是要求这个区间 $i$ 到 $i+2^j - 1$ 中的最大值。
这时我们发现，由于区间长度为2^j,所以是可以分割成左右两部分的，即 $i$ 到 $i + 2^{j-1}-1$ 和 $i + 2 ^ {j-1}$ 到 $i+2^j-1$
所以我们原区间的最大值就变成了两个区间的最大值的最大值，代码如下：

for(int i = 1 ; i <= lg[n] ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            if(j + num[i] - 1 <= n) 
                f[j][i] = max(f[j][i - 1],f[j + num[i - 1]][i - 1]);
        }
    }

区间查询：

首先，先说一个定理： $2^{\log x} > \frac{x}{2}$ 。
这个定理告诉我们，任意一个长度为 $x$ 的区间，都能被两端长度为 $2^{\log x}$ 的区间所覆盖。
所以我们的查询也变得很简单了，假如我们要查询区间 $[l,r]$ 的最大值，很显然，这段区间长度 $len=l-r+1$ 。
那么我们只要求出以 $l$ 为首，长度为 $2^{\log len}$ 的区间的最大值和以 $r$ 为尾，长度为 $2^{\log len}$ 的区间的最大值，就一定包括了整个区间的最大值。
所以我们可以知道 $[l,r]$ 中的最大值为 $\max(f[l][\log len],f[r -2^{\log len}+1][\log len])$ 。

例题：luogu P3865

题意：

给你一个长度为 $n$ 的的数列和 $m$ 组询问，询问序列中的最大值。

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

#define LL long long
const int N = 1e6 + 100;

int f[N][30],num[N];
int m,n,ans,lg[N];

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i++)
        scanf("%d",&f[i][0]);
    num[0] = 1,lg[0] = -1;
    for(int i = 1 ; i <= 30 ; i++)
        num[i] = num[i - 1] * 2;
    for(int i = 1 ; i <= n ; i++)
        lg[i] = lg[i / 2] + 1;
    for(int i = 1 ; i <= lg[n] ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            if(j + num[i] - 1 <= n) 
                f[j][i] = max(f[j][i - 1],f[j + num[i - 1]][i - 1]);
        }
    }
    for(int i = 1 ; i <= m ; i++) {
        int l,r;
        scanf("%d%d",&l,&r);
        int cnt = lg[r - l + 1];
        ans = max(f[l][cnt],f[r - num[cnt] + 1][cnt]);
        printf("%d \n",ans);
    }
    //system("pause");
    return 0;
}