RMQ的三种奇妙方法

这是2025年3月29号的截图 痛苦的一天

前言

用于记录不幸挂掉的某学校比赛的文章。。。

RMQ是什么

Range Max/Min Query，中文就是区间最大/最小值查询，简称RMQ，这篇文章主要探讨RMQ的3种解决方法。

题面

给你一个长度为$N$的正整数数组$A=(A_1,A_2,...A_N)$。

然后给你$M$个查询，每次查询给你左端点$l$和右端点$r$，回答$A$的第$l$个元素到第$r$个元素之间的这个区间中的元素的最大值。

$1 \leq N \leq 100000$

解题思路

首先你应该想到的

我都把这个看似很简单的题单独拎出来了，你如果还想着BF的话可以选择去往生堂把自己埋了，啊没错这个问题有几种奇妙的方法可以让程序跑的快多了！！！

ST表

思路

Sparse Table，中文就是稀疏表，是可以拿来解决可重复贡献问题的数据结构，简称ST表。

ST表基于倍增思想，具体实现是这样的：

我们定义$st_{i,j}$是对于区间[$i,i+2^{j}-1$]的答案。

那$st_{i,0}$就等于原数组的第$i$个元素，因为这个区间就是[$i,i$]，当然答案就是它自己。

那我们考虑转移，根据倍增的思想，$st$的第二维$j$就相当于倍增的时候跳了$2^{j} - 1$步，那所以不难想到转移方程：

$st_{i,j}=max(st_{i,j-1},st_{i+2^{j-1},j-1})$

那预处理就搞定了。那我们就来解决查询：

对于每个询问[$l,r$]，我们分成两部分：[$l,l+2^{k}-1$]和[$r-2^{k}+1,r$]，这里$k= \lfloor (r-l+1) \rfloor$。

时间复杂度

这个跑的不慢啊，起码比bf快。

稍微计算一下，可以算出我们可以做到$O(N log N)$预处理，$O(1)$的查询，它的代码实现其实也很简单，具体看下面：

代码

#include<bits/stdc++.h>
using namespace std;
int st[222222][30], n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> st[i][0];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
        }
    }
    int T;
    cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;
        int k = log2(r - l + 1);
        cout << max(st[l][k], st[r - (1 << k) + 1][k]) << '\n';
    }
    return 0;
}

线段树

思路

如果你熟练掌握线段树并且完全看懂了下面的方法，其实不难想到线段树也能解决这个问题，因为本身上面的就是把数组划分成了一个个线段然后解决，所以用线段树其实并不难实现

建树就不用多说了，大家肯定都会，只不过每个节点的val就是左右孩子val的最大值。

然后查询也和原本的差不多，每次判断和给定区间[$l,r$]之间的情况就好了。

时间复杂度

预处理$O(N)$，查询$O(log N)$。

和st表比较的话我会毫不犹豫选择st表，跑得更快啊

代码

#include<bits/stdc++.h>
using namespace std;
int a[111111], n;
struct node
{
    int val, l, r;
}bit[444444];
void build(int x, int l, int r)
{
    bit[x].l = l;
    bit[x].r = r;
    if (l == r) {
        bit[x].val = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    bit[x].val = max(bit[x * 2].val, bit[x * 2 + 1].val);
}
int query(int x, int l, int r)
{
    if (bit[x].l >= l && bit[x].r <= r) {
        return bit[x].val;
    }
    if (bit[x].l > r || bit[x].r < l) {
        return -2147483647;
    }
    return max(query(x * 2, l, r), query(x * 2 + 1, l, r));
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    int T;
    cin >> T;
    while (T--) {
        int l, r;
        cin >> l >> r;
        cout << query(1, l, r) << '\n';
    }
    return 0;
}

Four Russian的分块玄学优化

开头提到的那个考试给了我oiwiki的原文，结果瞅了半天没调出来直接没通过。。。

感觉这个代码比线段树都要难调。。。赛后看懂题解调了至少半个小时，我就很蒟蒻好吧

但是这个方法比上面两个都快了不少，具体看下面的吧，QAQ

思路

玄学玄学太玄学了！！！！！谁想到的啊

预处理：

考虑分块，我们把块大小设成$\sqrt{N}$，然后预处理出每一个块前缀和后缀的最大值。

然后我们对于每一个整块求出它的最大值，然后再维护任意两个整块之间的最大值。

查询：

如果给定的$l$和$r$不在同一区间内，我们可以直接回答$l$所在块的位置$l$的后缀RMQ、$r$所在块的位置$r$的前缀RMQ和$l$和$r$之间的整块之间的RMQ，三者之间的最大值。这些我们都是预处理过的，所以可以轻松得到。

但是如果在同一区间里的话，我们其实可以直接从$l$到$r$遍历一遍出结果即可，因为块的大小不会超过$\sqrt{N}$，所以也能轻松解决。

做法说完了，太玄学了QAQ

时间复杂度

预处理$O(n)$。查询如果在不同块内是$O(1)$，如果在同一块里是$O(\sqrt{n})$。

太快了吧，但是代码并不好写啊啊啊（至少对我来说）

UPD:如果出题人每次询问都给你同一个块内，其实可以随机微调块大小来防止被卡

这是作者对于洛谷上的RMQ模板题的两次测试：

测试1 测试2

第一次就正常按照$\sqrt{n}$分了块，第二次我随机微调了块的大小，可以发现第二个比第一个在大数据快了有$200$ms，所以就很棒

代码

#include<bits/stdc++.h>
using namespace std;
int n, a[111111], s1[111111][1111], s2[111111][1111], s[1111], st[1111][12];
int k;
vector<vector<int>> v;
int find(int x)
{
    return x / k;
}
void pre()
{
    for (int i = 0; i < v.size(); i++) {
        vector<int> tp = v[i];
        s1[i][0] = tp[0];
        for (int j = 1; j < tp.size(); j++) {
            s1[i][j] = max(tp[j], s1[i][j - 1]);
        }
        s2[i][tp.size() - 1] = tp[tp.size() - 1];
        for (int j = tp.size() - 2; j >= 0; j--) {
            s2[i][j] = max(tp[j], s2[i][j + 1]);
        }
        for (int j = 0; j < tp.size(); j++) {
            s[i] = max(s[i], tp[j]);
        }
    }
    for (int i = 0; i < v.size(); i++) {
        st[i][0] = s[i];
    }
    for (int j = 1; (1 << j) < v.size(); j++) {
        for (int i = 0; i + (1 << j) - 1 < v.size(); i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
        }
    }
}
int solvekuai(int l, int r)
{
    if (l > r) {
        return 0;
    }
    int kk = log2(r - l + 1);
    return max(st[l][kk], st[r - (1 << kk) + 1][kk]);
}
int solve(int l, int r)
{
    int lf = find(l), rf = find(r);
    if (lf == rf) {
        int maxx = a[l];
        for (int i = l + 1; i <= r; i++) {
            maxx = max(maxx, a[i]);
        }
        return maxx;
    } else {
        return max({s2[lf][l % k], s1[rf][r % k], solvekuai(lf + 1, rf - 1)});
    }
}
int main()
{
    cin >> n;
    k = sqrt(n);
    vector<int> tp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        tp.push_back(a[i]);
        if (tp.size() == k) {
            v.push_back(tp);
            tp.clear();
        }
    }
    int T;
    cin >> T;
    if (tp.size() > 0) {
        v.push_back(tp);
    }
    pre();
    while (T--) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << solve(l, r) << '\n';
    }
    return 0;
}

参考文献

本文部分灵感与图示来自oiwiki，链接放在下面了。

oiwiki-st表

oiwiki-rmq专题

啊哈可以去看看上面的链接