Range Sum Query and Range Update Query (RSQ 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をトップダウンに伝搬

    • 自身が持っている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をトップダウンに伝搬

    • 自身が持っているlazy値を半分ずつ左右に値を代入していく

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

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

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

計算量

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

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

実装

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

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(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] = lazy[2*i] = data[2*i-1] = data[2*i] = v >> 1
        lazy[i-1] = None
 
# 区間[l, r)をxに更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    v = x
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = v
        if L & 1:
            lazy[L-1] = data[L-1] = v
            L += 1
        L >>= 1; R >>= 1; v <<= 1
    for i in ids:
        data[i-1] = data[2*i-1] + data[2*i]
 
# 区間[l, r)内の合計を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

Verified

  • AOJ: "DSL_2_I: Range Query - RSQ and RUQ": source (Python3, 3.99sec)

戻る