Home
データ構造における演算の構造- アーベル群・モノイド・半群・etc...
ここではそれらの区別を行いますが、代数をかじった程度なのでアレです。演算のマークもアレです。(それはホントごめんなさい)(一発でわかるようにするため)
半群(M,⊕): 集合M,その上の二項演算があり、⊕が
- x⊕(y⊕z) = (x⊕y)⊕z (結合法則)
を満たす。逆元が存在すると群になる。
モノイド(M,e,⊕): 集合M,単位元eが存在し、その上の二項演算⊕があり、⊕が
- e⊕x=x⊕e=x (単位元)
- x⊕(y⊕z) = (x⊕y)⊕z (結合法則)
を満たす。(ここには半環も含まれる(結合順序が存在していても良い))
アーベル群(M,e,-1,⊕,⊕<->): 集合M,単位元eが存在し、その上の二項演算⊕があり、⊕が
- e⊕x=x⊕e=x (単位元)
- x⊕(y⊕z) = (x⊕y)⊕z (結合法則)
- ∀a, ∃a^-1; a*a^-1= e (任意の逆元)
- x⊕y = y⊕x (交換法則)
を満たす。更新されればmaxもよい.
要は可換な群
作用付きモノイド(M,(e,⊕),(v,*)): 集合M,単位元e,その上の二項演算⊕(query)があり、⊕,*がモノイド、集合Q上の二項演算*(update系)が
- a*(v1*v2) = (a*v1)*v2 (*における結合則)
- (a*v)⊕(b*v) = (a⊕b)*v (vの順序は関係ない)
を満たす。なんか分配則をイメージできれば良さそう(要加筆)
segtreeではしたがって、M(a)⊕M(b)->M(x), M(a)⊕Q(b)->M(x), Q(a)*Q(b)->Q(x)を満たす演算なら遅延評価できる。
交叉半束:
- (可換)
- (結合法則)
- x*x=x (冪等)(実質これをみたせばよい)
- (吸収)
を満たす。min/gcdは良いがsumは無理ということ。
TODO- 包含関係の図を書けると良い
モノイド
- SegmentTree,UnionFind
- したがってHL/BalancedTreeに適用可能
- min,max,sum,xor,gcd,lcm,abssum,prefix/suffixsum,..,ax+b,median,mode,..,
- ax+bなどは順序に注意
アーベル群
- BinaryIndexedTree,Potential-UnionFind
- sum,min,max,..
- addでないなら関係に注意
作用付きモノイド
- LazySegmentTree
- したがってHL/BalancedTreeに適用可能
- add/xor/ax+b(累乗でできるので)
- 可換でなくても良い
- M*M,Q*Qは自明だけどQ*Mはちゃんと考えて。
半束
- SparseTable
- max,min,gcd,..,
半群
- DisjointSparseTable
- 理解していない
