幺半群

幺半群描述一种能够连续合并、并允许“什么都不放”的操作。字符串连接是直接的例子：对三个片段 a、b、c，可以先把前两个连接成 ab，也可以先把后两个连接成 bc，再与剩余片段按原顺序连接，最终都得到 abc。空字符串接在任一侧都不改变内容。可是 ab 与 ba 不同，连接通常不交换。

结合律使长串 $a_1\ast \cdots \ast a_n$ 不必固定计算括号。例如可以先合并左半段和右半段，再合并两个结果。单位元则给空串一个结果：

这不是单独打补丁的特殊值；它保证把空片段插入任意分段计算都不改变答案。对重复元素，幂因此自然定义为 $a^0=e$、$a^{n+1}=a^n\ast a$，并满足 $a^{m+n}=a^m\ast a^n$。

“能够合并”与“能够撤回”是不同能力。在 $\mathbb{R}\cup \{-\mathrm{\infty }\}$ 上，最大值运算以 $-\mathrm{\infty }$ 为单位元，且满足结合律；但 $max(2,5)=max(4,5)=5$，合并后已无法区分此前是 $2$ 还是 $4$。因此删掉当前最大元素时，旧最大值通常不够用，还须保存其他候选值或额外计数。单位元只保证空输入可以参与组合，不保证其他输入可以被撤销。

三种不同的合并规律 ​

$({\mathbb{N}}_0,+,0)$ 是交换幺半群，$({\mathbb{N}}_0,\times ,1)$ 也是，但两者的运算与单位元都不同。讨论一个集合是否为幺半群时，必须同时说明运算。

字母表 $\mathrm{\Sigma }$ 上所有有限字符串组成 ${\mathrm{\Sigma }}^{\ast }$，以连接为运算、空串 $\epsilon$ 为单位元，称为自由幺半群。这里包括所有有限长度，不要求字符串长度统一，也不包含无限字符串。

一个集合 $X$ 上的全部自映射 $X\to X$，以函数复合理路函数复合Function composition · Composition of maps按先 f 后 g 的次序把映射串联为 g∘f。为运算、${\mathrm{id}}_X$ 为单位元，也构成幺半群。它允许不可逆操作：在 $X=\{0,1\}$ 上，把所有输入变成 $0$ 的函数 $c_0$ 满足 $c_0\circ c_0=c_0$，但没有逆。幂等性表示重复做不再变化，不表示一次操作没有丢失信息。

只会合并平均值为什么不够 ​

某一数据块有 $n$ 个数、总和为 $s$。若只保存平均值，直接平均两个块的均值会忽略块大小。一个元素的块 [0] 与三个元素的块 [4,4,4] 的均值分别为 $0,4$，平均这两个均值得到 $2$，而合并后的真实均值为 $3$。

保存摘要 $(s,n)\in \mathbb{R}\times {\mathbb{N}}_0$ 后，定义

结合性可以在两个坐标上分别验证：合并三个摘要得到 $(s+t+u,n+m+\ell )$，两种括号给出的坐标都相同；$(0,0)$ 则既不增加总和，也不增加数量。因此这给出交换幺半群。

上述两个数据块的摘要是 $(0,1)$ 与 $(12,3)$，合并为 $(12,4)$，最后读取 $12/4=3$。如果把第二块拆成 [4] 和 [4,4]，相应计算变成

分块方式改变，摘要仍一致。最后只在数量大于零时读取均值 $s/n$；空摘要 $(0,0)$ 可以参与合并，却不对应已经定义的均值。用于合并的数据与最终展示的统计量，因而可以是不同对象。

少一个条件会发生什么 ​

在至少含两个元素的集合上定义 $a\ast b=a$。它满足结合律，每个元素都是右单位元，却不存在左单位元，所以不是幺半群。要求双侧单位不能由一侧代替。

再看乘法幺半群 $({\mathbb{N}}_0,\times ,1)$。常值映射 $h(n)=0$ 满足 $h(ab)=h(a)h(b)$，但 $h(1)=0\ne 1$，所以只保持乘法还不够成为保单位的幺半群同态。

实现中还要区分数学运算与机器运算。实数加法结合，浮点加法却可能因舍入而不结合。数学上的任意括号重排保证，并不能不加条件地变成逐位相同的浮点并行结果。

同态把原数据的组合变成摘要的组合 ​

若 $h$ 是从字符串连接幺半群到某个摘要幺半群的同态，则

因此可以分别处理两个片段，再合并摘要；这正是检查分块计算是否保持含义的一种方法。反过来，自由幺半群上只要给每个字母指定一个目标幺半群元素，就能唯一地把整串映射定义成按顺序相乘。这种“先定义基本符号，再唯一扩展”的性质解释了自由二字。

有限自动机理路有限状态自动机Finite-state automaton · Finite automaton用有限个控制状态概括已读前缀，并沿带输入标号的转移识别有限字的模型家族。中，每个输入字母作用为一次状态变换；读入一个词就按读取顺序复合这些变换。把状态变换表示成幺半群元素，可以研究不同输入片段是否产生相同效果。若 $T_u$ 表示读完词 $u$ 后的状态变换，先读 $u$ 再读 $v$ 就有 $T_{uv}=T_v\circ T_u$，因为函数复合从右向左执行。要把 $u\mapsto T_u$ 写成保乘法的同态，可把目标运算定义为 $A\ast B=B\circ A$；必须先固定这个次序，不能直接把字符串顺序抄成通常的复合顺序。

对于维护区间摘要的树结构，只要摘要合并结合、并有空区间单位元，就能把子区间答案沿树合并。前缀扫描也能通过分块再组合计算所有前缀结果。若输入顺序有意义，例如矩阵乘积或字符串连接，分组可以调整，顺序仍须保留。

幺半群作用进一步描述“幺半群元素怎样变换某个集合”：单位元素不改变对象，两个元素连续作用等于其乘积的作用。它把抽象的可组合操作与具体状态变化联系起来，而不要求每次变化可逆。