Range Minimum Query (RMQ)

概要

以下のクエリが処理できるセグメント木の実装

  • \(a_i\) の値を \(x\) に更新

  • \(a_l, a_{l+1}, ..., a_{r-1}\) の最小値を求める

セグメント木の最も基本的な形。

特殊ケース高速化

以下のケースについては定数倍高速化ができる。

  • \(a_i\) の値を求める

  • prefix minimum: \(a_0, a_1, ..., a_{r-1}\) の最小値を求める

  • suffix minimum: \(a_l, a_{l+1}, ..., a_{N-1}\) の最小値を求める

prefix/suffixの最小値は、BITベースで計算することで高速化できる。

前計算では、 OEIS - A000265 と OEIS - A322250 をベースに計算する。

計算量

  • 更新: \(O(\log N)\)

  • 区間最小値: \(O(\log N)\)

実装

再帰的なセグメント木計算は、Pythonでは遅い(場合によってはTLEする)ので、再帰しない形で計算している。

# N: 処理する区間の長さ
N = ...

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

特殊ケース高速化

前計算として \(O(N)\) の処理を行う。

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)

# 前計算
I = []; J = []
for x in range(N0, 2*N0+1):
    y = (x // (x & -x)) >> 1
    I.append((y << 1)-1 if y else 0)
    J.append(y << 1)
J.reverse()

# 従来のupdateと同じ
def update(k, x):
    k += N0
    data[k-1] = x
    while k > 1:
        k >>= 1
        data[k-1] = min(data[2*k-1], data[2*k])

# query [0, r)
def lquery(r):
    return min(map(data.__getitem__, __lquery(r)))
def __lquery(r):
    while r:
        yield I[r]
        r -= (r & -r)

# query [l, N0)
def rquery(l):
    return min(map(data.__getitem__, __rquery(l)))
def __rquery(l):
    r = N0 - l
    while r:
        yield J[r]
        r -= (r & -r)

# query [k, k+1)
def query1(k):
    return data[k+N0-1]

Verified

  • AOJ: "DSL_2_A: Range Query - Range Minimum Query (RMQ)": source (Python3, 1.22sec)

  • AtCoder: "AtCoder Regular Contest 026 - C問題: 蛍光灯": source (Python3, 1914ms)

参考

戻る