概要
遅延セグメント木は様々な区間操作が で可能です。
一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは
に悪化してしまいます。
本稿では空間計算量を に抑えたまま、
で処理する手法を提案します。
また、積に限らず一般のモノイドについても同様に
回の演算で区間への代入と和を取る処理が可能です。
アルゴリズム
基本的には遅延セグメントツリーと同様です。
を代入するクエリの時、
として
について
を計算し、保存しておきます。
セグメントツリーはノードの要素数が
の形しか存在しないため、これで
でクエリの処理が可能になりました。
さて、このまま愚直に処理をすると空間計算量が になってしまいます。
ここで
となったときに全ての遅延を解消し、前計算をすべて破棄します。
この処理は
で可能なため、全体でも 1 クエリの計算量は
で保たれていることになります。
実装
https://noshi91.github.io/Library/library/gomi/assign_segment_tree.cpp.html
