遅延伝搬セグメント木の可視化
ここの解説とソースのdocが食い違っている時はソースの方が正しい、doctestで回帰テストしてるから。
遅延伝搬セグメント木の可視化
範囲作用・範囲縮約の可能な遅延伝搬セグメント木になる
ここでは「まだ値に適用されてない(遅延された)作用のテーブル」を双対セグメント木で、「値」をセグメント木で別々に管理して可能な限りここまでの実装を使う
この二つの木がどういう相互作用をするのかを描き出す目的
結果、範囲作用と下への伝搬は分けたテーブルそれぞれの操作では難しいので二つのテーブルを束ねて一つのテーブルとして扱う仕組みを導入した
値のセグメント木を普通に初期化する
python>>> set_depth(4)
>>> value_table = [""] * SEGTREE_SIZE
>>> set_items(value_table, [chr(i + ord("a")) for i in range(8)])
>>> full_up(value_table, lambda x, y: f"{x}{y}")
>>> debugprint(value_table)
| abcdefgh |
| abcd | efgh |
| ab| cd| ef| gh|
|a|b|c|d|e|f|g|h|作用の双対セグメント木を単位作用で初期化する
python>>> action_unity = PowAction(1)
>>> action_table = [action_unity] * SEGTREE_SIZE
>>> debugprint(action_table)
| ^1 |
| ^1 | ^1 |
| ^1 | ^1 | ^1 | ^1 |
|^1|^1|^1|^1|^1|^1|^1|^1|作用の合成を適切に定義する
例えば単位元を空リストにしておいて、作用の合成はリストの結合にするとか
ここでは作用が冪乗なので
(^n) + (^m) = (^(n*m)) という合成ができるpythondef action_composite(new_action, old_action):
return PowAction(new_action.value * old_action.value)ここで作用のテーブルに対して範囲更新すれば良い、と勘違いしていた
実際には値テーブルも同時に更新する必要がある
まず作用によって値がどう更新されるかを定義する
def action_force(action, value): ... 次に作用と値の対のテーブルに対して、作用の合成と値の更新を同時にやる関数を作る
pythondef combined_action(new_action):
def f(args):
action, value = args
return (
action_composite(new_action, action),
action_force(new_action, value))
return fこれで範囲作用ができる
(先に上からの伝播が必要だが、今は伝播するものがないので飛ばしてる)
当初僕は「まず作用のテーブルにだけ書き込み、その後必要に応じて値の更新と作用の子への伝搬が行われる」と勘違いしていた
木の末端においても値の更新は必要なのに、伝搬させる子供がいないので条件分岐が必要になってしまう
python>>> range_update(combined_table, L, R, combined_action(PowAction(2)))
>>> debugprint(action_table, 3)
| ^1 |
| ^2 | ^1 |
| ^1 | ^1 | ^2 | ^1 |
| ^1| ^1| ^1| ^1| ^1| ^1| ^1| ^1|
>>> debugprint(value_table, 3)
| abcdefgh |
| (abcd)^2 | efgh |
| ab | cd | (ef)^2| gh |
| a | b | c | d | e | f | g | h |値の更新はセグメント木的に上に伝搬する
ここは値のテーブルだけに対する操作、セグメント木部分
python>>> up_propagate(value_table, up(L), lambda x, y: f"{x}{y}")
>>> up_propagate(value_table, up(R), lambda x, y: f"{x}{y}")
>>> debugprint(value_table, 3)
| (abcd)^2(ef)^2gh |
| (abcd)^2 | (ef)^2gh |
| ab | cd | (ef)^2| gh |
| a | b | c | d | e | f | g | h |なぜ範囲全体ではなく両端からの伝播でいいかはmaspyさんの記事を参照
なお下記の実装だと伝搬経路を先に計算して上にも下にも使いまわしている
上方向の伝搬は途中で合流するので、この方法は合流以降が省けてて良い
次に範囲作用するとき(ここから省略のないフルバージョンの範囲作用)
まず範囲の両端に関して遅延された作用を下に伝播する
作用が下に降りるタイミングで、下の値も更新する
先に来た作用が先に値の更新に使われることを担保するため
これを双対セグメント木での下への伝搬で表現できるかなと思ったが、難しかった
伝搬した後、親が単位作用に戻る実装なのだが「作用と値の対」に対しては適当ではない
作用は単位作用に戻るが、値は更新されないので。
そこで専用に書いた
pythondef down_propagate_force(table, pos, action_composite, action_force, action_unity):
max_level = pos.bit_length() - 1
for level in range(max_level):
i = pos >> (max_level - level)
action, value = table[i]
a, v = table[i * 2]
table[i * 2] = (
action_composite(action, a),
action_force(action, v))
a, v = table[i * 2 + 1]
table[i * 2 + 1] = (
action_composite(action, a),
action_force(action, v))
table[i] = (action_unity, value)下に伝搬してから、範囲作用して、値を上に伝搬する、これでひとかたまり
python>>> L = 1
>>> R = 5
>>> down_propagate_force(
... combined_table, up(L),
... action_composite, action_force, action_unity)
>>> down_propagate_force(
... combined_table, up(R),
... action_composite, action_force, action_unity)
>>> debugprint(action_table)
| ^1 |
| ^1 | ^1 |
| ^1 | ^2 | ^1 | ^1 |
|^2|^2|^1|^1|^2|^2|^1|^1|
>>> debugprint(value_table)
| (abcd)^2(ef)^2gh |
| (abcd)^2 | (ef)^2gh |
| (ab)^2| (cd)^2| (ef)^2| gh |
|a^2|b^2| c | d |e^2|f^2| g | h |
>>> range_update(combined_table, L, R, combined_action(
... PowAction(3), action_composite, action_force))
>>> debugprint(action_table, 3)
| ^1 |
| ^1 | ^1 |
| ^1 | ^6 | ^1 | ^1 |
| ^2| ^6| ^1| ^1| ^6| ^2| ^1| ^1|
>>> debugprint(value_table, 3)
| (abcd)^2(ef)^2gh |
| (abcd)^2 | (ef)^2gh |
| (ab)^2 | ((cd)^2)^3 | (ef)^2 | gh |
| a^2 |(b^2)^3| c | d |(e^2)^3| f^2 | g | h |
>>> up_propagate(value_table, up(L), lambda x, y: f"{x}{y}")
>>> up_propagate(value_table, up(R), lambda x, y: f"{x}{y}")
>>> debugprint(value_table, 3)
| a^2(b^2)^3((cd)^2)^3(e^2)^3f^2gh |
| a^2(b^2)^3((cd)^2)^3 | (e^2)^3f^2gh |
| a^2(b^2)^3 | ((cd)^2)^3 | (e^2)^3f^2 | gh |
| a^2 |(b^2)^3| c | d |(e^2)^3| f^2 | g | h |範囲縮約
下に伝搬してから値のテーブルに対して普通に範囲縮約する
python>>> L = 3
>>> R = 5
>>> down_propagate_force(
... combined_table, up(L),
... action_composite, action_force, action_unity)
>>> down_propagate_force(
... combined_table, up(R),
... action_composite, action_force, action_unity)
>>> debugprint(value_table)
| a^2(b^2)^3((cd)^2)^3(e^2)^3f^2gh |
| a^2(b^2)^3((cd)^2)^3 | (e^2)^3f^2gh |
| a^2(b^2)^3 | ((cd)^2)^3 | (e^2)^3f^2 | gh |
| a^2 |(b^2)^3| c^6 | d^6 |(e^2)^3| f^2 | g | h |
>>> value_unity = ""
>>> print(range_reduce(value_table, L, R, lambda x, y: f"{x}{y}", value_unity))
d^6(e^2)^3Range add, range sumをやることを考える
掛け算
a * b と累乗 (^ n) は (a * b) ^ n = (a ^ n) * (b ^ n) の関係が成り立つ分配法則と呼ぶ
Range add, range sumだと
a + b と (+ n) の間に分配法則が成り立たない (a + b) + n = (a + n) + (b + n) ではないサイズが4であるノードに(+1)をしたら、値は4増えないといけない
プログラム的な解決: 作用が値だけでなくノードのサイズも引数に取るようにする
数学的な解決: 値の定義域をノードサイズとの直積にする
親のノードサイズは子のノードサイズの和なので、上への伝搬で適切に構築できる
(+) =
lambda (v1, s1), (v2, s2): (v1 + v2, s1 + s2) (+n) =
lambda (v, s): v + s * n ここまでやってきた「二つの木の貼り合わせで表現する」というアプローチだと作用と値の対のテーブルに対して、作用の合成と値の更新を同時にやる関数(combined_action)にノードの位置やサイズが渡ってこないので数学的アプローチしか取れない
そろそろ現実的な速度で動かすこととのギャップが大きくなりすぎなのでここではやらないことにする
「作用と値の対のテーブル」を作らないで両方引数として渡す形の実装でAOJの4種類の遅延伝搬セグメント木の問題が解けてるのでそちらを参照
Related Pages
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×Sparse Table×rmq×atcoder→
- →交叉半束×結合法則×交換法則×冪等性×セグメント木×スパーステーブルとセグメント木×最小共通祖先×オイラーツアー×range_minimum_query×2d_sparse_table×2d_range_minimum_query×スパーステーブル→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]