Range Minimum Query and Range Add Query (RMQ and RAQ)

概要

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

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

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

Starry Sky Tree と呼ばれているらしい。

具体的計算

遅延評価セグメント木(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\) ] += x; 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 = [0]*(2*N0)
lazy = [0]*(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 not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[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] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; 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_H: Range Query - RMQ and RAQ": source (Python3, 4.60sec)

参考

戻る