遅延セグ木に乗るモノイド・作用付きモノイドの条件

• $S=(S, \cdot, e)$: データのモノイド
• $F=(F, \circ, \mathrm{id})$: 作用のモノイド
• $*\colon F\times S \to S$ : 作用
  • $F\to \operatorname{Set}(S,S),\ f\mapsto f * -$ が準同型であること
    • $\mathrm{id}* x = x$
    • $(f\circ g)x = f(g*x)$
    • (これは自然と満たしているはず？）
  • $f *- \colon S \to S$ がモノイドの二項演算を保つこと
    • $f (x\cdot y) = (fx) \cdot (f*y)$
    • ($f * e = e$ は課していないらしい）
      • 実際、区間変更・区間最小取得などは、これを満たしていない実装が多い

参考: atcoder.github.io/ac-library/document_ja/lazysegtree.html

典型的な遅延セグ木のクエリ

• 区間アフィン・区間和取得

  

• 区間アフィン・区間min/max取得

  

• 区間加算

  • 傾き1の区間アフィン

• 区間変更

  • 傾き0の区間アフィン

• 区間 0,1 反転、区間 0の個数 & 1の個数取得 (range xor range sum)

可換図式

• 可換図式

遅延セグ木を使った問題の例

• 新規に遅延セグ木を設計
  • Library Practice Contest L - Lazy Segment Tree
    • 区間 0, 1 反転・区間転倒数取得
  • ABC357 F -Two Sequence Queries