双対セグメント木の下への伝搬
「値を上書きする」の範囲作用がどう定義されるべきか
範囲作用はノードが上にあるか下にあるかでどちらが後かわからない
そこで値をタイムスタンプ付きにして、下への伝搬は「タイムスタンプの新しい方を取る」二項演算にした
これは改めて考えてみると下記を意味している
作用が可換だと無意識に前提した実装にしていた
可換でない"上書き作用"の時に正しく動作しない
タイムスタンプを付与することで可換なmax演算に変えた
範囲作用の前に下への伝搬を正しくやっていないことが問題
正しく双対セグメント木を作ったが「作用の合成が可換」を見落としていた
範囲作用を2回やって、fとgが順不同で重なっているデモ
下への伝搬が可換ならここで順番が入れ替わってても問題ない
code:python
>> range_update(table, 3, 10, lambda x: "f")
>> range_update(table, 5, 15, lambda x: "g")
>> debugprint(table)
| 0 |
| 0 | 0 |
| 0 | f | g | 0 |
| 0 | 0 | 0 | g | f | 0 | g | 0 |
|0|0|0|f|0|g|0|0|0|0|0|0|0|0|g|0|
可換でない時の正しいやり方
2つ目の範囲作用の前に下への伝搬をしておく
次の範囲作用で書き換えるセルの上のセルが下に降りてることが保証される
範囲作用させてるlambda x: "g"は、下伝搬の二項演算lambda x, y: x if x else yのxに"g"が入ったもの
code:python
>> table = 0 * SEGTREE_SIZE >> range_update(table, 3, 10, lambda x: "f")
>> down_propagate(table, up(5), lambda x, y: x if x else y, 0)
>> down_propagate(table, up(15), lambda x, y: x if x else y, 0)
>> debugprint(table)
| 0 |
| 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | f | f | 0 | 0 | 0 |
|0|0|0|f|f|f|0|0|0|0|0|0|0|0|0|0|
>> range_update(table, 5, 15, lambda x: "g")
>> debugprint(table)
| 0 |
| 0 | 0 |
| 0 | 0 | g | 0 |
| 0 | 0 | 0 | g | f | 0 | g | 0 |
|0|0|0|f|f|g|0|0|0|0|0|0|0|0|g|0|