群论基础

[981377660LMT]

G为非空集合，如果在G上定义的二元运算op *，满足
（1）封闭性（Closure）：对于任意a，b∈G，有a*b∈G
（2）结合律（Associativity）：对于任意a，b，c∈G，有（a*b）*c=a*（b*c）
（3）幺元 （Identity）：存在幺元e，使得对于任意a∈G，e*a=a*e=a
（4）逆元：对于任意a∈G，存在逆元a^-1，使得a^-1*a=a*a^-1=e
则称（G，*）是群，简称G是群。

• 半群：满足 封闭性 和 结合律。
• 幺半群：有 幺元 的半群。
• 群：有 逆元 的幺半群。

[981377660LMT]

1. Monoid，幺半群，顾名思义，指的是有幺元(单位元，Identity)的半群(semigroup)。
2. 线段树只能维护满足结合律的信息，即只能维护一个幺半群序列。而树状数组只能维护交换群序列。 如果树状数组只用来查询前缀，可以维护幺半群。
3. 有逆元的幺半群就是群。
4. 交换群又叫阿贝尔群。例如整数加法群是交换群。
5. *具有逆元的 monoid (也就是群)可以由欧拉序列 O(logn) 查询。例如加法。 不具有逆元的 monoid (也就是幺半群)可以由重链剖分 O(lognlogn) 查询。例如 min/max/gcd。**

[981377660LMT]

/**
 * 群（Group）是代数结构的一种，它包括一个集合和一个二元运算。
 * 群需要满足以下四个性质：
 * 1. 闭合性：对于群中的任意两个元素，其运算结果仍然是群中的元素。
 * 2. 结合性：对于群中的任意三个元素，无论如何结合，其运算结果仍然是群中的元素。
 * 3. 存在单位元：群中存在一个元素，对于群中的任意元素，与其运算都能得到另一个群中的元素。
 * 4. 存在逆元：群中的每个元素都有一个与之对应的元素，对于群中的任意元素，与其运算都能得到单位元。
 */
interface Group<E> {
  e(): E
  op(e1: E, e2: E): E
  inv(e: E): E
  readonly commutative?: boolean
}

/**
 * 半群（SemiGroup）是代数结构的一种，它包括一个集合和一个二元运算。
 * 半群需要满足以下两个性质：
 * 1. 闭合性：对于半群中的任意两个元素，其运算结果仍然是半群中的元素。
 * 2. 结合性：对于半群中的任意三个元素，无论如何结合，其运算结果仍然是半群中的元素。
 */
interface SemiGroup<E> {
  op(e1: E, e2: E): E
}

/**
 * 幺半群（Monoid）是代数结构的一种，它包括一个集合和一个二元运算。
 * 幺半群需要满足以下三个性质：
 * 1. 闭合性：对于幺半群中的任意两个元素，其运算结果仍然是幺半群中的元素。
 * 2. 结合性：对于幺半群中的任意三个元素，无论如何结合，其运算结果仍然是幺半群中的元素。
 * 3. 存在单位元：幺半群中存在一个元素，对于幺半群中的任意元素，与其运算都能得到另一个幺半群中的元素。
 */
interface Monoid<E> extends SemiGroup<E> {
  e(): E
}

/**
 * 阿贝尔群是满足交换律的群。
 */
interface AbleGroup<E> extends Group<E> {
  readonly commutative: true
}

// 树状数组维护的代数结构通常是一个可逆的交换半群（Commutative Semigroup）。
//   如果只需要查询前缀, 那么可以使用一个幺半群（Monoid）。
// 线段树维护的代数结构通常是一个幺半群（Monoid）。
// ST表维护的代数结构通常是一个半群（SemiGroup）。

[981377660LMT]

https://emthrm.github.io/cp-library/algebraic_structure.html

[981377660LMT]