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

• $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

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

• range affine / range sum

  

• range affine / range min max

  

• range add

  • 傾き1の range affine

• range update

  • 傾き0の range affine

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

• range chmin / range min max

• range chmin chmax / range min max

• range chmin chmax add / range min max

• range xor add range xor sum

• range update range xor sum

可換図式