双対セグメント木の下への伝搬

• DSL 2 D Range Update Queryではこう書いた
  • 「値を上書きする」の範囲作用がどう定義されるべきか
  • 範囲作用はノードが上にあるか下にあるかでどちらが後かわからない
  • そこで値をタイムスタンプ付きにして、下への伝搬は「タイムスタンプの新しい方を取る」二項演算にした
• これは改めて考えてみると下記を意味している
  • 作用が可換だと無意識に前提した実装にしていた
  • 可換でない"上書き作用"の時に正しく動作しない
  • タイムスタンプを付与することで可換なmax演算に変えた
• 範囲作用の前に下への伝搬を正しくやっていないことが問題
  • 点取得しか必要ない時に値のセグメント木を省くのが半分遅延セグメント木
  • さらに作用の合成が可換である時に、下への伝搬をサボるのが双対セグメント木
  • 正しく双対セグメント木を作ったが「作用の合成が可換」を見落としていた

範囲作用を2回やって、fとgが順不同で重なっているデモ

• 下への伝搬が可換ならここで順番が入れ替わってても問題ない 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"が入ったもの 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|

付録: 下への伝搬の影響範囲

双対セグメント木 セグメント木の可視化