セグメント木で使える演算子 segment tree, lazy 〃(自分用メモ)

目的

  • これってセグ木でできる?をまとめる
  • 参考コードを探すときの高速化

モノイド(下記を満たしていればsegtreeできる!)

セグ木と遅延〃

  • セグ木
    • 1箇所更新
    • 範囲取得
  • 遅延〃
    • 範囲更新
    • 範囲取得

モノイドの例(セグ木)(随時追記)

#include <atcoder/segtree>
using namespace atcoder; // 忘れがち

ll op(ll a, ll b) { return min(a, b); }
ll e() { return inf; }
ll target;
bool f(ll v) { return v < target; }

// min seg tree
segtree<ll, op, e> seg(A);

遅延セグ木の例

beetさんのまとめ「セグ木に載せるモノイドまとめ(未完)」

  • 和、積、min, max, gcd, lcm は乗るそう
    • 和(できるやろ)
    • 積(できるやろ)
    • min(アルメリアさんのblog)
    • max(アルメリアさんのblog)
    • gcd(本記事の上に具体例URL)範囲加算のlazy不可。範囲積ならできそう?
    • lcm(まだ。単位元=1だしできそう)
  • 他にもたくさん?

セグ木がいらない例