基于压位与猫树分治的 O(n)-O(1) 的 RMQ

· · 算法·理论

老实倍增,很枯燥吧。下文以 \max 为例。

简介

这是一种在 Word-RAM Model 下被认为是时间复杂度 O(n)-O(1) 的一种 RMQ 算法。根据 AI 在 n,q=10^6 下的测试,通常情况下的实现被认为预处理常数与基于按 w 分块倍增表相同,随机查询下常数为其的一半,空间严格更优的做法。

做法

下文默认假装将 n 补到 2 的整数次幂,叶子节点是第 0 层。

考虑猫树分治解决 RMQ 问题的过程。我们建立一颗类似线段树的树,并在每个节点维护所有左半区间的后缀与右半区间的前缀的 \max。这样,建树的时候只需要 O(n\log n) 的时空复杂度,并在查询的时候 O(1) 定位节点并查询左右端点的信息即可。

现在考虑我们不记录具体的 \max 值是什么,而是记录所有作为其前缀/后缀 \max 的位置在哪里。将所有在分治同层的位向量压到一个数组内部,这样,可以将空间压缩到 O(\frac{n\log n}{w})。

尝试将时间复杂度也压到这个部分。由于我们查询的时候需要查询前缀/后缀的 max,也就是相当于查询位向量上的某个值为 1 的前驱/后继。

于是分为得到这些位向量和预处理支持 O(1) 查询的信息。

现在考虑所有右半的前缀,左半的后缀同理。考察一个向上合并两个儿子区间的过程。一开始,所有节点内部区间就是这个位置,因此所有位置都是前缀 \max。合并两个儿子的时候,相当于是保留所有左儿子的前缀 \max,并不断弹出右儿子所有不大于左儿子区间 \max 的前缀 \max。

因此,某个位置在猫树上作为前缀 \max 的所有层一定是一个层上的前缀(显然向上被删除了不可能再重新加回来)。因此,我们只要得到这个层上的前缀位置 p,然后在第 p 层的位向量上将该位置置 1,最后统一从大到小将第 i 层的位向量或上第 i+1 层的位向量即可。

现在考虑快速得到这个位置 p。我们可以使用单调栈在 O(n) 的时间复杂度内求出来所有位置 i 左边第一个比它大的数的位置 L_i。那么,相当于是 L_i 一定要在节点所代表的区间外。对于第 p 层第 i 个位置所属块,由于补全,这个块编号就是 \frac{i}{2^p}。那么显然,\frac{i}{2^p}\neq \frac{L_i}{2^p} 等价于 p\le \operatorname{highbit}(i \operatorname{xor} L_i)。

现在得到位向量以后,考虑预处理以支持 O(1) 查询。考虑我们已经存进了一个压位的数组中,于是我们可以另开一个数组记录当前的前缀中最后一个 1 的位置在哪里。查询时候,如果该位置所在压位的块中前缀有 1,那么可以直接查询,否则访问这个记录的数组。

于是我们得到了一个 O(\frac{n\log n}{w})-O(1) 的 RMQ 解决方案。

实现

这是一份能通过 P3865 【模板】ST 表 & RMQ 问题 的代码。

#include <bits/stdc++.h>
#define N 100010
#define ull unsigned long long
#define clz __builtin_clzll
#define ctz __builtin_ctzll
using namespace std;
int n, m;
int a[N];
int stk[N], tp;
int l[N], r[N];
struct info { ull pv, sv; int pre, suf; }T[18][(N >> 6) + 1];
inline int hb(unsigned x) { return 31 - __builtin_clz(x); }
inline int qry(int l, int r)
{
    if (l == r) return l;
    static ull s, p;
    static int h, u, v;
    h = hb(l ^ r);
    const info& x = T[h][l >> 6], & y = T[h][r >> 6];
    s = x.sv & (~0ull << (l & 63)), p = y.pv & (~0ull >> (~r & 63));
    u = s ? (l & ~63) + ctz(s) : x.suf, v = p ? (r & ~63) + 63 - clz(p) : y.pre;
    return a[u] > a[v] ? u : v;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        while (tp && a[stk[tp]] < a[i]) r[stk[tp--]] = i;
        l[i] = stk[tp], stk[++tp] = i;
    }
    while (tp) r[stk[tp--]] = n + 1;
    for (int i = 1; i <= n; i++) T[l[i] ? hb(l[i] ^ i) : 17][i >> 6].pv |= 1ull << (i & 63), T[r[i] != n + 1 ? hb(r[i] ^ i) : 17][i >> 6].sv |= 1ull << (i & 63);
    for (int p = 17; ~p; p--)
    {
        if (p != 17) for (int i = 0; i <= n >> 6; i++) T[p][i].pv |= T[p + 1][i].pv, T[p][i].sv |= T[p + 1][i].sv;
        int pos = 0;
        for (int i = 0; i <= n >> 6; i++) T[p][i].pre = pos, pos = T[p][i].pv ? (i << 6) + 63 - clz(T[p][i].pv) : pos;
        pos = 0;
        for (int i = n >> 6; ~i; i--) T[p][i].suf = pos, pos = T[p][i].sv ? (i << 6) + ctz(T[p][i].sv) : pos;
    }
    static int l, r;
    while (m--) cin >> l >> r, cout << a[qry(l, r)] << '\n';
    return 0;
}

可以看到实现难度跟基于压位的倍增表大差不差。

后记

本做法由我在学习小波树的时候,神游之时思考到的一种做法。也是在退役之前希望给 OI 做出点贡献吧。