日々drdrする人のメモ

今日も明日もdrdr

非再帰版の遅延評価セグメント木の実装メモ

再帰版の遅延評価セグメント木(Segment Tree with Lazy Propagation)の実装メモ。

自分の実装メモとして、非再帰版のセグメント木を前提に、非再帰版の遅延評価セグメント木の書き方をまとめとく。

以下を参考にしている。

Segment Treeをちょっと高速化したい - komiyamの日記
Efficient and easy segment trees - Codeforces

前提: 非再帰版セグメント木

セグメント木は区間処理を行う際、チェックする区間を全て列挙しながら非再帰に処理することができる。

問題: Range Minimum Query (RMQ) | Aizu Online Judge

# Range Minimum Query
N0 = 2**(N-1).bit_length()
INF = 2**31-1
# 0-indexedで管理
data = [INF]*(2*N0)

# 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

提出コード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3158592#1


遅延評価セグメント木の概要

セグメント木上で、各区間を計算する必要があるまで更新しない(値の伝搬を遅延させる)ようにしたデータ構造。

区間の更新処理と区間の取得処理が {O(\log N)}でできる。


例えば、以下の2種類のクエリを処理する問題が解ける。 (RMQ and RUQ)

  • クエリ1(RMQ):  {a_l, a_{l+1}, ..., a_{r-1}}の中の最小値を求める
  • クエリ2(RUQ):  {a_l, a_{l+1}, ..., a_{r-1}}の値を {x}に更新

遅延評価セグメント木の構成

f:id:smijake3:20181008235925p:plain
区間[0, 32)を管理するセグメント木の構造

区間 {[l, r)}には以下の値を持たせる

  • data: 区間の現在の値
    • dataの値は、セグメント木の親ノードに伝搬させる
  • lazy: 遅延させている値
    • lazyの値は、セグメント木の子ノードに伝搬させる

遅延評価セグメント木のクエリ処理の概要

f:id:smijake3:20181009002806p:plain
区間[3, 22)を更新する例
(赤 = dataとlazyの値を伝搬させる区間, 青 = dataとlazyの値を更新する区間)

区間 {I = [l, r)}に対して処理を行う場合は通常のセグメント木と同様に、処理する区間を含む区間(上の図の青い区間)の値の更新や取得を行えばよい。

ただし、値の書き換えや値の取得等、処理する時点で青い区間の最新の値が必要になるケースが存在する。
そして、最新にするためには青い区間の全ての先祖ノード(上の図の赤い区間)で遅延させている値lazyを伝搬させる必要がある。

区間 {I = [l, r)}の更新処理

以下の手順で区間 {[l, r)}を更新する。

  1. 更新する区間を部分的に含んだ区間(図の赤い区間)について、lazyの値をトップダウンで子ノードに伝搬させながら、dataの値を更新
    • 赤い区間の個数は  {(2 \lceil \log N \rceil + 1)} 個以下
    • 数を足すクエリ等、遅延によって計算順序が前後してよい場合は、ここで伝搬させなくてもよい
  2. 値を更新する区間(図の青い区間)のdataとlazyの値を更新
    • 青い区間の個数は  {\max(2 \lceil \log N \rceil - 2, 1)} 個以下
    • 再帰版セグメント木と同じように区間を列挙する
  3. 更新する区間を部分的に含んだ区間(図の赤い区間)について、dataの値を根までボトムアップに伝搬させながら、dataの値を更新
    • 1の伝搬を行わなかった場合、ここでlazyの値を考慮する必要がある
区間 {I = [l, r)}の取得処理

以下の手順で区間 {[l, r)}の値を求める。

  1. 更新する区間を部分的に含んだ区間(図の赤い区間)について、lazyの値をトップダウンで子ノードに伝搬させながら、dataの値を更新
    • 赤い区間の個数は  {(2 \lceil \log N \rceil + 1)} 個以下
  2. 値をチェックする区間(図の青い区間)のdataの値をチェックし、求める値を計算
    • 青い区間の個数は  {\max(2 \lceil \log N \rceil - 2, 1)} 個以下
    • 再帰版セグメント木と同じように区間を列挙する

伝搬する区間の列挙方法

再帰で伝搬処理を行う場合、更新される区間を部分的に含んだ区間(図の赤い区間)を列挙する必要がある。

これは難しくなく、区間 {[l, l+1)}区間 {[r, r+1)}からボトムアップ区間を列挙するだけで伝搬すべき区間が全て列挙できる。

f:id:smijake3:20181101234423p:plain
区間[3, 22)を処理する時に伝搬すべき区間を列挙する例
(区間[3, 4)と区間[22,23)からボトムアップに列挙することで全て列挙できる)

ボトムアップに列挙した区間の内、先頭何個か伝搬する必要のない区間が含まれることがあるため、うまく取り除くことで伝搬させる区間を減らすことができる。(例えば、上の例の区間[20, 22)は値を更新する区間に含まれ、伝搬させる必要はない)

これは、 {L = l + N_0, R = r + N_0} ( {N_0 = 2^{\lceil \log N \rceil}}とする)の値をチェックし、
 {L} {R}についてそれぞれ先頭の(trailing zero bitsの数+1)個の区間を取り除くことでうまくいく。

1-indexedで区間を管理した時、インデックス {2k}区間からインデックス {k}区間ボトムアップに移動し続ける限り、伝搬する区間でないと考えればよい。

f:id:smijake3:20181101230818p:plain
区間[4, 22)を処理する例。
インデックス36(4+32)と54(22+32)からボトムアップに列挙し伝搬する区間を取得する
(赤: 伝搬すべき区間, 黃: 伝搬する必要のない区間)

以下がインデックスを降順で列挙する関数

# 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
LV = (N-1).bit_length()
N0 = 2**LV
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1

コード実装 (RMQ and RUQ)

ここで、"RMQ and RUQ"を実装する。

  • クエリ1(RMQ):  {a_l, a_{l+1}, ..., a_{r-1}}の中の最小値を求める
  • クエリ2(RUQ):  {a_l, a_{l+1}, ..., a_{r-1}}の値を {x}に更新

問題: RMQ and RUQ | Aizu Online Judge

両方の処理で用いる、伝搬処理は以下の関数に区間インデックスを渡して処理する。

# 1-indexedで単調増加のインデックスリストを渡す
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
区間更新 (RUQ)
def update(l, r, x):
    *ids, = gindex(l, r)
    # 1. トップダウンにlazyの値を伝搬
    propagates(*ids)
 
    # 2. 区間[l, r)のdata, lazyの値を更新
    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

    # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
区間取得 (RMQ)
def query(l, r):
    # 1. トップダウンにlazyの値を伝搬
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    # 2. 区間[l, 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

コード実装 (RMQ and RAQ)

次に、"RMQ and RAQ" (Starry Sky Tree)を実装する。

  • クエリ1(RMQ):  {a_l, a_{l+1}, ..., a_{r-1}}の中の最小値を求める
  • クエリ2(RAQ):  {a_l, a_{l+1}, ..., a_{r-1}} {x}を加算

問題: RMQ and RAQ | Aizu Online Judge

伝搬処理は以下の関数に区間インデックスを渡して処理する。

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
区間更新 (RAQ)

更新時の加算の順序は前後してよいため、lazyの値を伝搬させずに区間更新のみを行う。
そして、ボトムアップにdataの値を更新する際にlazyの値を考慮する。

def update(l, r, x):
    # 2. 区間[l, r)のdata, lazyの値を更新
    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

    # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
    for i in gindex(l, r):
        data[i-1] = min(data[2*i-1], data[2*i]) + lazy[i-1]
区間取得 (RMQ)

"RMQ and RUQ"のRMQと同様

def query(l, r):
    # 1. トップダウンにlazyの値を伝搬
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    # 2. 区間[l, 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