要么改变世界,要么适应世界

RMQ问题之ST表

2021-04-28 19:30:05
110
目录

前言

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

一些概念

  • RMQ:Range Minimum/Maximum Query, 中文为区间最值查询 。
  • 可重复贡献问题:官方术语解释起来不好解释,举个例子:假如我需要求前面8个数字的最值,我可以先求这8个数字中偏前面的6个中的最值number1,然后再求这8个数字中偏后面的最值number2,然后求number1number2中二者最优者即可,这个过程你会发现中间的几个数字被重复计算了。
  • 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)是对len2对数并下取整,最上面的区间和最小面的区间长度都是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;
}
历史评论
开始评论