RMQ问题【模板】

概念

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。

解决 RMQ 问题的主要方法有两种，分别是 ST 表和线段树。本文主要讲 ST 表。

ST表

$ST$ 表，即 $Sparse-Table$ 算法，它预处理的时间是 $O(nlogn)$，但是查询时间只需要 $O(1)$，且常数非常小。但是不支持修改操作。最重要的是，这个算法非常好写，并且不容易出错。

$ST$ 表是基于倍增思想，令 $d(i, j)$ 表示从 $i$ 开始的，长度为 $2^j$的一段元素中的最小值，则可以用推递的方式计算 $d(i, j)$：$d(i, j) = max\{d(i,j-1), d(i + 2^{j-1}, j-1) \}$，$f[i][0] = a[i]$，即把待查询区间平均分成了两部分。

注意 $2^j \leq n$，因此 $d$ 数组中的元素个数不超过 $n log n$，而每一项都可以在常数时间内计算完成，故总时间为 $O(n log n)$。

ST表模板题

洛谷 P3865【模板】ST表

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

分析：由于时限很紧，需要预处理log，将每次查询的复杂度从 $O(logn)$ 降至 $O(1)$.

代码：

#include<bits/stdc++.h>

using namespace std;

const int logn = ;  //log n

const int maxn = * + ;

int a[maxn], f[maxn][logn], Logn[maxn];

int n, m;   //n个元素，m次查询

inline int read()

{

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

void pre()

{

    Logn[] = ;

    Logn[] = ;

    for(int i = ;i < maxn;i++) Logn[i] = Logn[i/] + ;

}

void RMQ_init()

{

    pre();

    for(int j = ;j <= logn;j++)

        for(int i = ;i + ( << j) -  <= n;i++)

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

}

int RMQ(int L, int R)

{

    int s = Logn[R - L + ];

    return max(f[L][s], f[R - ( << s) + ][s]);

}

int main()

{

    n = read(); m = read();

    for(int i = ;i <= n;i++)  f[i][] = read();

    RMQ_init();

    for(int i = ;i < m;i++)

    {

        int x, y;

        x = read(); y = read();

        printf("%d\n", RMQ(x, y));

    }

    return ;

}

注意：

输入输出数据一般很多，建议开启输入输出优化
每次用 std::log 重新计算 log 函数值并不值得，建议采用递推式预处理 $log$

参考链接：https://oi-wiki.org/ds/sparse-table/#__comments

巴特西

RMQ问题【模板】

概念

ST表

ST表模板题

最新文章

热门文章