Range Minimum Query and Range Update Query (RMQ and RUQ)

概要

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

  • \(a_l, a_{l+1}, ..., a_{r-1}\) の値を \(x\) に更新

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

具体的計算

遅延評価セグメント木(Segment Tree with Lazy Propagation)の実装では、 各区間Iには区間の値value[ \(I\) ]と遅延させている値lazy[ \(I\) ]を持たせる。

区間更新

区間 \(I = [l, r)\) の値更新処理では、以下を行う。

  1. 更新する区間が含まれる全ての区間で遅延させている値lazyをトップダウンに伝搬

    • 伝搬させる区間は \(2 \lceil \log N \rceil + 1\) 個以下

  2. 区間 \(I\) に含まれる(最小個の)区間の値を全て更新

    • 更新する区間は高々 \(2 \lceil \log N \rceil - 2\) 個

    • value[ \(I\) ] = lazy[ \(I\) ] = x

  3. 更新する区間を含む全ての区間の値valueをボトムアップに更新

    • 遅延値を伝搬した1の区間を更新する

最小値計算

区間 \(I = [l, r)\) 内の最小値計算は、以下のように行う。

  1. 2の計算で参照する区間が含まれる全ての区間で遅延させている値lazyをトップダウンに伝搬

    • 伝搬させる区間は \(2 \lceil \log N \rceil + 1\) 個以下

  2. 区間 \(I\) に含まれる(最小個の)区間から最小値を求める

    • 確認する区間は高々 \(2 \lceil \log N \rceil - 2\) 個

計算量

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

  • 最小値計算: \(O(\log N)\)

実装

高速化のために非再帰で実装している。 いろいろ試したけど、伝搬対象の区間を列挙してから計算するのが手軽だった。

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

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)
 
# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
 
# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None
 
# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
 
# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    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

Verified

  • AOJ: "DSL_2_F: Range Query - RMQ and RUQ": source (Python3, 3.70sec)

戻る