目的
- これってセグ木でできる?をまとめる
- 参考コードを探すときの高速化
モノイド(下記を満たしていれば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);
- max
- sum
- or
- タコヤキ (ax+b)
- gcd
- Make One With GCD 2 https://yukicoder.me/problems/no/1036
- AC https://yukicoder.me/submissions/473183
- ACL ver TLE O(N logN logN) https://yukicoder.me/submissions/593163
- ACL ver (セグ木上の二分探索 & 高速なgcd) AC✅ https://yukicoder.me/submissions/593173
- 区間加算&区間GCDのlazy segは?❌
- 載らないらしい motsu-xe.hatenablog.com/entry/2020/05/13/194454
- C - GCD on Blackboard (ACL公式対応)
- Make One With GCD 2 https://yukicoder.me/problems/no/1036
- XOR
- 範囲に+1してmod2(区間加算)、区間和
- H - Counting 1's
- AC https://atcoder.jp/contests/s8pc-2/submissions/26257275
- かけ算
- (long double)
- AOJ 3132 AC https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5957754#1
遅延セグ木の例
beetさんのまとめ「セグ木に載せるモノイドまとめ(未完)」
- 和、積、min, max, gcd, lcm は乗るそう
- 他にもたくさん?
セグ木がいらない例
- 和(BITでいい)
- XOR (累積XOR)でいい
- 本当?区間に1をXOR(flip), 区間和 https://atcoder.jp/contests/s8pc-2/submissions/1574140
- ※更新がない場合に限る