https://noshi91.hatenablog.com/entry/2019/10/05/203704

概要

遅延セグメント木は様々な区間操作が $\Theta ( \log N )$ で可能です。一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは $\Theta ( \log ^2 N )$ に悪化してしまいます。
本稿では空間計算量を $\Theta ( N )$ に抑えたまま、 $\rm amortized \, \Theta ( \log N )$ で処理する手法を提案します。また、積に限らず一般のモノイドについても同様に $\Theta ( \log N )$ 回の演算で区間への代入と和を取る処理が可能です。

アルゴリズム

基本的には遅延セグメントツリーと同様です。
$x$ を代入するクエリの時、 $N = 2 ^ {k}$ として $i \in \lbrack 0 , k \rbrack$ について $x ^ {2 ^ {i}}$ を計算し、保存しておきます。セグメントツリーはノードの要素数が $2^i$ の形しか存在しないため、これで $\Theta ( \log N )$ でクエリの処理が可能になりました。
さて、このまま愚直に処理をすると空間計算量が $\Theta ( N + Q \log N )$ になってしまいます。ここで $Q \gt N / \log N$ となったときに全ての遅延を解消し、前計算をすべて破棄します。この処理は $\Theta ( N )$ で可能なため、全体でも 1 クエリの計算量は $\rm amortized \, \Theta ( \log N )$ で保たれていることになります。

実装

https://noshi91.github.io/Library/library/gomi/assign_segment_tree.cpp.html