非再帰版の遅延評価セグメント木の実装メモ
非再帰版の遅延評価セグメント木(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
遅延評価セグメント木の概要
セグメント木上で、各区間を計算する必要があるまで更新しない(値の伝搬を遅延させる)ようにしたデータ構造。
例えば、以下の2種類のクエリを処理する問題が解ける。 (RMQ and RUQ)
- クエリ1(RMQ): の中の最小値を求める
- クエリ2(RUQ): の値をに更新
遅延評価セグメント木の構成
各区間には以下の値を持たせる
- data: 区間の現在の値
- dataの値は、セグメント木の親ノードに伝搬させる
- lazy: 遅延させている値
- lazyの値は、セグメント木の子ノードに伝搬させる
遅延評価セグメント木のクエリ処理の概要
区間に対して処理を行う場合は通常のセグメント木と同様に、処理する区間を含む区間(上の図の青い区間)の値の更新や取得を行えばよい。
ただし、値の書き換えや値の取得等、処理する時点で青い区間の最新の値が必要になるケースが存在する。
そして、最新にするためには青い区間の全ての先祖ノード(上の図の赤い区間)で遅延させている値lazyを伝搬させる必要がある。
伝搬する区間の列挙方法
非再帰で伝搬処理を行う場合、更新される区間を部分的に含んだ区間(図の赤い区間)を列挙する必要がある。
これは難しくなく、区間と区間からボトムアップに区間を列挙するだけで伝搬すべき区間が全て列挙できる。
ボトムアップに列挙した区間の内、先頭何個か伝搬する必要のない区間が含まれることがあるため、うまく取り除くことで伝搬させる区間を減らすことができる。(例えば、上の例の区間[20, 22)は値を更新する区間に含まれ、伝搬させる必要はない)
これは、 (とする)の値をチェックし、
とについてそれぞれ先頭の(trailing zero bitsの数+1)個の区間を取り除くことでうまくいく。
1-indexedで区間を管理した時、インデックスの区間からインデックスの区間にボトムアップに移動し続ける限り、伝搬する区間でないと考えればよい。
以下がインデックスを降順で列挙する関数
# 伝搬される区間のインデックス(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): の中の最小値を求める
- クエリ2(RUQ): の値をに更新
問題: 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): の中の最小値を求める
- クエリ2(RAQ): にを加算
問題: 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