勉強会に参加したい方は概要を確認してください。

定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

セグメント木・遅延セグメント木（復習）

遅延セグメント木の作用モノイドと総和モノイドの間には準同型と呼ばれる以下の性質が要求されていた。

$$ f(a\cdot b) = f(a) \cdot f(b) $$

例えば、区間加算の作用と区間 min の間には以下の性質が成り立つ。

$$ \min\{a,b\} + x = \min\{a+x, b+x\} $$

この性質があるため、区間の作用を遅延させることが出来た。

もう少し掘り下げると、区間総和が求まってさえいれば、区間作用後の区間総和の値が直ちに求められるというのが、作用を遅延させる上で大事な性質になっている。

以下では、区間作用後の区間総和の値を高速に求めることが難しいクエリが出てくる問題をいくつか紹介し、それらの問題が遅延セグメント木を数行改造することで解けることを示す。

準同型でない（が、特定の条件を満たす）作用モノイドクエリを解く特殊な遅延セグメント木。

<aside>

作用
- 区間代入（ $a_i \leftarrow x; i\in[l,r)$ ）
- 区間切り捨て除算（ $a_i \leftarrow \lfloor a_i / x\rfloor; i\in[l,r)$ ）
クエリ
- 区間 sum </aside>