遅延伝搬セグメント木の可視化

ソースコードはこちら
- ここの解説とソースの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))という合成ができる python

def action_composite(new_action, old_action):
    return PowAction(new_action.value * old_action.value)

ここで作用のテーブルに対して範囲更新すれば良い、と勘違いしていた
- 実際には値テーブルも同時に更新する必要がある
まず作用によって値がどう更新されるかを定義する
- def action_force(action, value): ...
- 次に作用と値の対のテーブルに対して、作用の合成と値の更新を同時にやる関数を作る python

def 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さんの記事](https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B72)を参照
    - [下への伝搬の影響範囲](/ja/%E4%B8%8B%E3%81%B8%E3%81%AE%E4%BC%9D%E6%90%AC%E3%81%AE%E5%BD%B1%E9%9F%BF%E7%AF%84%E5%9B%B2)
    - [up演算](/ja/up%E6%BC%94%E7%AE%97)
    - なお下記の実装だと伝搬経路を先に計算して上にも下にも使いまわしている
        - 上方向の伝搬は途中で合流するので、この方法は合流以降が省けてて良い
        - [RMQ and RUQ (遅延評価セグメント木) - yaketake08's 実装メモ](https://tjkendev.github.io/procon-library/python/range_query/rmq_ruq_segment_tree_lp.html)

次に範囲作用するとき(ここから省略のないフルバージョンの範囲作用)
- まず範囲の両端に関して遅延された作用を下に伝播する
  - 作用が下に降りるタイミングで、下の値も更新する
  - 先に来た作用が先に値の更新に使われることを担保するため
- これを双対セグメント木での下への伝搬で表現できるかなと思ったが、難しかった
  - 伝搬した後、親が単位作用に戻る実装なのだが「作用と値の対」に対しては適当ではない
    - 作用は単位作用に戻るが、値は更新されないので。
  - そこで専用に書いた

python

def 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)^3

Range 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種類の遅延伝搬セグメント木の問題が解けてるのでそちらを参照
  - 汎用で実用的な遅延伝搬セグメント木の実装

(C)NISHIO Hirokazu / Converted from Markdown (ja)
Source: [GitHub] / [Scrapbox]