线性RMQ(±1 RMQ)

What · 是什么

线性 RMQ 指『O(n) 预处理 + O(1) 查询』的区间最小值问题最优解法，由 Farach-Colton 与 Bender(2000)给出。思路：先把一般 RMQ 规约到 LCA 问题(构造笛卡尔树，区间最小值 ⇔ 两节点的 LCA)，再把 LCA 规约回 ±1 RMQ(欧拉序相邻深度差为 ±1)。±1 RMQ 用分块法：块大小 b≈⌈log n⌉/2，块内所有可能的 ±1 差分模式(签名)总数只有 2^(b−1)，同签名块共享预计算 O(b²) 的块内查询表；块间用 ST 表 O((n/b)log(n/b))≈O(n/b·b)=O(n)。综合得 O(n) 预处理 O(1) 查询。

Why · 为什么

How · 实现

伪代码

build(a):  # 直接对 ±1 数组做分块线性 RMQ
  b = max(2, bit_length(n)//2)   # 块大小 ≈ log n / 2
  分块, 记录每块 min 与 min 位置
  块间建 ST 表(块最小值)
  每块记录 ±1 差分签名(bitmask)
  按签名共享缓存块内 [i,j] 最小位置表(O(b²))
query(l, r):
  若同块: 查块内缓存
  否则: 左块内 + 右块内 + 块间 ST 查询取最小

Python 实现

from sparse import SparseTable


class RMQLinear:
    """线性RMQ (±1 RMQ): O(n) 预处理 + O(1) 查询。
    数组需满足相邻元素差为 ±1 (任意RMQ先经笛卡尔树规约成 ±1 序列)。
    分块 + 块内位掩码签名 + 块间ST表。"""
    def __init__(self, a):
        self.a = a
        self.n = len(a)
        if self.n == 0:
            return
        self.b = max(2, (self.n).bit_length() // 2)
        self.nb = (self.n + self.b - 1) // self.b
        self.blk_min = []
        self.blk_min_idx = []
        for bi in range(self.nb):
            l = bi * self.b
            r = min(self.n, l + self.b)
            mn = min(a[l:r])
            self.blk_min.append(mn)
            self.blk_min_idx.append(l + a[l:r].index(mn))
        self.st = SparseTable(self.blk_min, min)
        self.sig = []
        for bi in range(self.nb):
            l = bi * self.b
            r = min(self.n, l + self.b)
            sig = 0
            for i in range(l + 1, r):
                if a[i] - a[i - 1] == 1:
                    sig |= (1 << (i - l - 1))
            self.sig.append(sig)
        self.cache = {}

    def _blk_query(self, bi, i, j):
        l = bi * self.b
        w = min(self.b, self.n - l)
        i = min(i, w - 1)
        j = min(j, w - 1)
        key = (self.sig[bi], w)
        if key not in self.cache:
            pos = [[0] * w for _ in range(w)]
            for s in range(w):
                best = s
                pos[s][s] = s
                for e in range(s + 1, w):
                    if self.a[l + e] < self.a[l + best]:
                        best = e
                    pos[s][e] = best
            self.cache[key] = pos
        return l + self.cache[key][i][j]

    def query(self, l, r):
        """[l, r] 闭区间最小值下标"""
        if l > r:
            return -1
        bi, bj = l // self.b, r // self.b
        if bi == bj:
            return self._blk_query(bi, l - bi * self.b, r - bi * self.b)
        left = self._blk_query(bi, l - bi * self.b, min(self.b, self.n - bi * self.b) - 1)
        right = self._blk_query(bj, 0, r - bj * self.b)
        best = left if self.a[left] <= self.a[right] else right
        if bi + 1 <= bj - 1:
            mid_val = self.st.query(bi + 1, bj - 1)
            for idx in range(bi + 1, bj):
                if self.blk_min[idx] == mid_val:
                    cand = self.blk_min_idx[idx]
                    if self.a[cand] < self.a[best]:
                        best = cand
                    break
        return best

    def query_val(self, l, r):
        return self.a[self.query(l, r)]


if __name__ == "__main__":
    import random
    for _ in range(2000):
        n = random.randint(1, 40)
        a = [0]
        for _ in range(n - 1):
            a.append(a[-1] + random.choice([-1, 1]))
        rmq = RMQLinear(a)
        for _ in range(100):
            l = random.randint(0, n - 1)
            r = random.randint(l, n - 1)
            assert rmq.query_val(l, r) == min(a[l:r + 1]), (a, l, r)
    for n in [1, 2, 3, 5, 10]:
        for step in [1, -1]:
            a = [i * step for i in range(n)]
            rmq = RMQLinear(a)
            for l in range(n):
                for r in range(l, n):
                    assert rmq.query_val(l, r) == min(a[l:r + 1])
    print("rmq-linear OK")

易错点

• 直接对一般数组跑 ±1 模板忘记先规约到 ±1(笛卡尔树欧拉序)
• 块长 b 过大导致签名 2^(b−1) 爆炸，应 b≈⌈log n/2⌉
• 块内缓存键未包含块宽 w，最后一块宽度不同会越界
• 块间 ST 只给最小值不给位置，忘记再映射回块下标
• 把 O(n log n) 的 ST 表误称为线性 RMQ，两者预处理不同

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/graph/rmq_linear.html
• OI Wiki✓ https://oi-wiki.org/ds/sparse-table/