双対セグメント木

双対セグメント木という概念について - うさぎ小屋 双対セグメント木 / 遅延セグメント木を半分にするテク - HackMD

• 僕が双対セグメント木だと思ってたもの、半分の遅延セグメント木なのでは
  • 双対セグメント木の下への伝搬

    • 作用が可換だと無意識に前提した実装にしていた

    • 可換でない”上書き作用”の時に正しく動作しない

    • タイムスタンプを付与することで可換なmax演算に変えた

  • これが下記に対応するのでは

    • 双対セグメント木

    • 作用が 区間加算・区間chmin のような 作用させる順番を入れ替えても結果が変わらない 作用のとき、作用側を通常のセグメント木のように処理することができ、若干速い

    • 区間代入のやり方

    • (時間, 代入する値) をペアにして chmax するとできる。