RMQ问题之ST表

前言

ST表和线段树类似，用于快速求解区间问题，二者的建立时间都是O(nlogn)，但是ST表查询的时间达到了O(1)，虽然说不支持区间更新，线段树支持更新，更新花费时间O(logn)，查询花费O(logn)

一些概念

• RMQ:Range Minimum/Maximum Query， 中文为区间最值查询 。
• 可重复贡献问题：官方术语解释起来不好解释，举个例子：假如我需要求前面8个数字的最值，我可以先求这8个数字中偏前面的6个中的最值number1，然后再求这8个数字中偏后面的最值number2，然后求number1和number2中二者最优者即可，这个过程你会发现中间的几个数字被重复计算了。
• ST表：一种数据结构，英文名为Sparse Table，即稀疏表。

原理

构建

ST表应用了倍增以及动态规划的思想。

以求给定序列number[]的最大值为例：

定义f[i][j]为区间[i, 2^j - 1]内的最大值（即包括number[i]），特别的，f[i][0]=number[i]。

i					   							i + 2 ^ j - 1
|------------------------------------------------|

对于上述区间，长度为2^(j)，为了求f[i][j]，我们可以先求前半段的最大值，再求后半段的最大值，然后取二者中较大者。

i					   							i + 2 ^ j - 1
|------------------------------------------------|
i          		i+2^(j-1)-1    i+2^(j-1) 			i + 2 ^ j - 1
|--------------------------|   |----------------------|

即状态转移方程为：

f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])

查询

ST表构建后之后，我们还不能直接拿过来简单使用，因为根据ST表的定义我们可以知道，当需要求的区间长度是2的整数幂的时候，f[][]才为所需要的答案。例如我要求的是left=3,right=8的区间中的最大值。

3        6
|--------|
3            8
|------------|
3                 10
|-----------------|

此时f[3][2]代表上面的区间，f[3][3]代表下面的区间，而我们要求的是中间的区间。

此时可重复贡献问题的优势就体现出来了。

我们可以把问题一般化，假设要求的是[left,right]的最大值，此时log2(right - left)不是整数，此时我们可以把所求的区间分为两个子区间（当然，这两个区间之间是有重叠的），如下图所示：

log2(len)是对len取2对数并下取整，最上面的区间和最小面的区间长度都是2的次幂，可以很方便地分别使用

f[left][x]
f[right - 2^x + 1][x]

来表示，其中x=log2(right - left + 1)并向下取整（加1应该很好理解）,此时中间所要求的区间即：

f[left][right] = max(f[left][x], f[right - 2^x + 1][x])

算法实现

题目来源：洛谷【模板】ST表

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const int MAX_N = 1e5 + 20;
int f[MAX_N][25], n, m;
inline int read(){
    int sum = 0, flag = 0;
	char ch = getchar();
	while (!isdigit(ch)){if (ch=='-') flag = 1; ch = getchar();}
	while (isdigit(ch)){sum = (sum << 1) + (sum << 3) + ch-48;ch = getchar();}
	return flag ? -sum : sum;
}
void pre(){
    for(int i = 1; i <= n; i++)f[i][0] = read();
    // 2^17 > 1e5
    // 为什么以 j 开始进行枚举 i？
    // 因为 j 是控制区间长度的，保证 2^j 的区间是之前就已经求好的
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
}
int main(){
    n = read(), m = read();
    pre();
    int l, r, xlog2, ans;
    for (int i = 1; i <= m; i++){
        l = read(), r = read();
        xlog2 = log2(r - l + 1);
        ans = max(f[l][xlog2], f[r - (1 << xlog2) + 1][xlog2]);
        printf("%d\n", ans);
    }
    return 0;
}