每周一算法：倍增法求区间最大最小值（RMQ）-Toy模板网

这篇具有很好参考价值的文章主要介绍了每周一算法：倍增法求区间最大最小值（RMQ）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

RMQ

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。使用倍增思想解决 RMQ 问题的方法是 ST 表（Sparse Table，稀疏表）。ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题是指对于运算 $\operatorname{opt}$ ，满足 $x\operatorname{opt} x=x$ ，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 $\max(x,x)=x$ ， $g c d$ 有 $\operatorname{gcd}(x,x)=x$ ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次。另外， $\operatorname{opt}$ 还必须满足结合律才能使用 ST 表求解。

题目链接

题目链接：【模板】ST 表

题目描述

这是一道 ST 表经典题——静态区间最大值

请注意最大数据时限只有 0.8s，数据强度不低，请务必保证你的每次查询复杂度为 $O (1)$ 。若使用更高时间复杂度算法不保证能通过。

如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

函数返回值为读入的第一个整数。

快速读入作用仅为加快读入，并非强制使用。

题目描述

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 $N, M$ ，分别表示数列的长度和询问的个数。

第二行包含 $N$ 个整数（记为 $a_i$ ），依次表示数列的第 $i$ 项。

接下来 $M$ 行，每行包含两个整数 $l_i,r_i$ ，表示查询的区间为 $l_i,r_i]$ 。

输出格式

输出包含 $M$ 行，每行一个整数，依次表示每一次询问的结果。

样例 #1

样例输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

样例输出 #1

提示

对于 $30\%$ 的数据，满足 $1\le N,M\le 10$ 。

对于 $70\%$ 的数据，满足 $1\le N,M\le {10}^5$ 。

对于 $100\%$ 的数据，满足 $1\le N\le {10}^5$ ， $1\le M\le 2\times{10}^6$ ， $a_i\in[0,{10}^9]$ ， $1\le l_i\le r_i\le N$ 。

算法思想

ST 表基于倍增思想，可以做到 $O(n\log n)$ 预处理， $O (1)$ 回答每个询问。但是不支持修改操作。

基于倍增思想，考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$ 步的话，询问时的复杂度仍旧是 $O(\log n)$ ，效率较低。

由于区间最大值是一个具有可重复贡献性质的问题。哪怕用来求解的预处理区间有重叠部分，只要这些区间合并是所求的区间，最终计算出的答案就是正确的。举个例子：

每周一算法：倍增法求区间最大最小值（RMQ）,每周一算法,算法,青少年编程,信息学竞赛,c++

区间 $[2, 5]$ 的最大值为 $5$ ，区间 $[4, 7]$ 的最大值为 $7$ ，区间 $[2, 7]$ 的最大值为 $max\{5,7\}=7$ 。

通过ST表，使用至多两个预处理过的区间就可以覆盖询问区间，也就是说询问时的时间复杂度可以被降至 $O (1)$ ，在处理有大量询问的题目时十分有效。

预处理ST表

状态表示

$f [i] [j]$ 表示区间 $i,i+2^j-1]$ 的最大值。

状态计算

要计算区间 $i,i+2^j-1]$ 的最大值，区间大小为 $2^j$ ，相当于从位置 $i$ 跳了 $2^j-1$ 步，依据倍增的思想，可以将整个区间一分为二，左侧区间 $i,i+2^{j-1}-1]$ ，右侧区间 $i+2^{j-1},i+2^j-1]$ ，大小均为 $2^{j-1}$ ，如下图所示：
每周一算法：倍增法求区间最大最小值（RMQ）,每周一算法,算法,青少年编程,信息学竞赛,c++
那么状态转移方程：

$f[i][j]=max\{f[i][j-1],f[i+2^{j-1}][j-1]\}$

初始状态

$f[i][0]=a_i$

查询区间最值

对于每个询问 $[L, R]$ ，把它成两个部分 $L,L+2^k-1]$ 与 $R-2^k+1,R]$ ，其中 $k=\lfloor log_2(R-L+1)\rfloor$ ，两部分的最值就是答案。文章来源地址https://www.toymoban.com/news/detail-782759.html

时间复杂度

预处理 ST 表的时间复杂度为 $O(n\log n)$
回答每个询问的时间复杂度 $O (1)$

代码实现

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 20;
int n, a[N], f[N][M];
//创建ST表
void create() {
    //初始状态
    //f[i][0]表示从i开始长度为2^0的区间最值为a[i]本身
    for(int i = 1; i <= n; i ++) f[i][0] = a[i];
    int k = log2(n);
    //枚举区间长度指数j
    for(int j = 1; j <= k; 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]);
}
//利用ST表查询区间[L,R]的最大值
int query(int L, int R) {
    int k = log2(R - L + 1);
    return max(f[L][k], f[R - (1 << k) + 1][k]);
}
int main()
{
    int m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);;
    create();
    while(m --) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d\n", query(L, R));
    }
}