代数运算结构

本章主线：二元运算 → 结合律、单位元与逆元 → 半群、幺半群与群 → 同态 → 算法中的可合并信息。

1 为什么研究运算结构

许多算法表面上处理的对象不同：

• 区间和处理数字；
• 区间最小值处理大小关系；
• 矩阵快速幂处理矩阵；
• 函数复合处理映射；
• 字符串拼接处理字符串。

它们能够使用相似算法，往往不是因为对象相同，而是因为所使用的运算具有相同性质。

因此，应当区分：

• 运算作用在什么对象上；
• 运算满足哪些性质；
• 算法真正依赖哪些性质。

---

2 二元运算与封闭性

设 $S$ 是一个集合。

若一个规则 $\circ$ 能够把任意两个元素 $a,b\in S$ 组合成一个新元素 $a\circ b$，并且结果仍属于 $S$，则称 $\circ$ 是 $S$ 上的二元运算。

形式化地，

$$\circ:S\times S\to S.$$

这里包含封闭性要求：对任意 $a,b\in S$，都有 $a\circ b\in S$。

例如，整数加法是整数集合上的二元运算，因为两个整数之和仍是整数。

自然数减法通常不是自然数集合上的二元运算，因为 $2-5=-3\notin\mathbb N$。

矩阵乘法只有在矩阵尺寸匹配时才能进行。固定为所有 $n\times n$ 矩阵后，乘法结果仍是 $n\times n$ 矩阵，因此形成封闭运算。

---

3 结合律

若对任意 $a,b,c\in S$，都有

$$(a\circ b)\circ c=a\circ(b\circ c),$$

则称运算 $\circ$ 满足结合律。

结合律表示：多个元素按原顺序组合时，括号位置不会影响结果。

例如：

• 整数加法满足结合律；
• 整数乘法满足结合律；
• 字符串拼接满足结合律；
• 矩阵乘法满足结合律；
• 函数复合满足结合律。

减法不满足结合律，因为一般有 $(a-b)-c\ne a-(b-c)$。

---

3.1 结合律为什么重要

设区间 $[l,r]$ 被分成 $[l,m]$ 与 $[m+1,r]$。

若区间信息可以通过运算 $\circ$ 合并，则整体信息为

$$\operatorname{Info}(l,r) = \operatorname{Info}(l,m)\circ \operatorname{Info}(m+1,r).$$

线段树会按照不同划分方式递归组合区间。

若运算不满足结合律，不同树形结构可能得到不同结果，答案就不稳定。

因此：

区间信息能够被线段树稳定维护，最核心的条件通常是合并运算满足结合律。

---

4 单位元

若存在元素 $e\in S$，使得对任意 $a\in S$，都有

$$e\circ a=a\circ e=a,$$

则称 $e$ 是运算 $\circ$ 的单位元。

单位元表示“什么也没有做”。

常见例子：

• 加法单位元是 $0$；
• 乘法单位元是 $1$；
• 字符串拼接的单位元是空串；
• 矩阵乘法的单位元是单位矩阵；
• 函数复合的单位元是恒等映射；
• 最小值运算常以 $+\infty$ 作为扩展意义下的单位元；
• 最大值运算常以 $-\infty$ 作为扩展意义下的单位元。

---

4.1 单位元与空区间

查询数据结构时，有时某一侧没有贡献。

若存在单位元，就可以让空部分返回 $e$，因为 $e\circ a=a$。

例如区间和查询中，空区间返回 $0$；区间最小值查询中，空区间返回 $+\infty$。

单位元使边界处理更加统一。

---

5 逆元

设运算 $\circ$ 的单位元为 $e$。

若对元素 $a\in S$，存在元素 $a^{-1}\in S$，使得

$$a\circ a^{-1}=a^{-1}\circ a=e,$$

则称 $a^{-1}$ 是 $a$ 的逆元。

逆元表示可以撤销一个元素的作用。

常见例子：

• 加法中 $a$ 的逆元是 $-a$；
• 非零实数乘法中 $a$ 的逆元是 $1/a$；
• 异或运算中 $a$ 的逆元仍是 $a$，因为 $a\oplus a=0$；
• 可逆矩阵的逆元是逆矩阵；
• 双射的逆元是逆映射。

并不是所有元素都一定存在逆元。例如整数乘法中，$2$ 的乘法逆元 $1/2$ 不属于整数集合。

---

5.1 逆元与前缀差分

设前缀和为 $P_i=a_1+a_2+\cdots+a_i$。

因为加法存在逆元，所以区间和可以由两个前缀值相减得到：

$$a_l+a_{l+1}+\cdots+a_r=P_r-P_{l-1}.$$

这里的减法就是加上逆元。

一般地，若运算构成可逆结构，常可以由“整体结果”和“一部分结果”恢复剩余部分。

---

6 交换律

若对任意 $a,b\in S$，都有 $a\circ b=b\circ a$，则称运算满足交换律。

常见满足交换律的运算：

• 加法；
• 普通乘法；
• 最大值；
• 最小值；
• 按位与、按位或、按位异或。

常见不满足交换律的运算：

• 字符串拼接；
• 矩阵乘法；
• 函数复合。

结合律与交换律是不同性质。

线段树通常只要求结合律，不要求交换律。对于不满足交换律的运算，必须严格保持元素原有顺序。

例如区间矩阵乘积与区间字符串拼接都可以用线段树维护。

---

7 幂等性

若对任意 $a\in S$，都有 $a\circ a=a$，则称运算具有幂等性。

常见幂等运算包括：

• $\min(a,a)=a$；
• $\max(a,a)=a$；
• $a\land a=a$；
• $a\lor a=a$；
• 集合并集 $A\cup A=A$；
• 集合交集 $A\cap A=A$。

加法通常不具有幂等性，因为 $a+a$ 一般不等于 $a$。

---

7.1 幂等性与重复覆盖

若运算具有幂等性，同一信息被重复计算不会改变结果。

稀疏表查询区间最值时，可以使用两个有重叠的区间覆盖目标区间。

重叠部分会被计算两次，但因为 $\min$ 与 $\max$ 具有幂等性，答案不受影响。

区间和不能这样处理，因为重叠元素会被重复累加。

---

8 吸收性与零元

若存在元素 $z$，使得对任意 $a\in S$，都有 $z\circ a=a\circ z=z$，则称 $z$ 是吸收元或零元。

例如普通乘法中的 $0$ 满足 $0\cdot a=a\cdot0=0$。

布尔与运算中的 false 是吸收元。

吸收元与单位元不同：

• 单位元不会改变另一个元素；
• 吸收元会覆盖另一个元素。

---

9 半群

一个集合 $S$ 配合一个满足结合律的二元运算 $\circ$，称为半群，记作 $(S,\circ)$。

半群只要求：

1. 封闭性；
2. 结合律。

例如：

• 非空字符串在拼接下构成半群；
• 正整数在加法下构成半群；
• 固定大小的方阵在矩阵乘法下构成半群。

半群已经足以支持“按任意括号方式合并”的思想。

---

10 幺半群

若半群中还存在单位元，则称其为幺半群。

幺半群要求：

1. 封闭性；
2. 结合律；
3. 单位元。

例如：

• 整数在加法下构成幺半群，单位元为 $0$；
• 字符串在拼接下构成幺半群，单位元为空串；
• 方阵在矩阵乘法下构成幺半群，单位元为单位矩阵；
• 映射在函数复合下构成幺半群，单位元为恒等映射。

许多区间数据结构实际维护的就是幺半群。

---

11 群

若幺半群中每个元素都有逆元，则称其为群。

群要求：

1. 封闭性；
2. 结合律；
3. 单位元；
4. 每个元素都有逆元。

例如，整数在加法下构成群：

• 运算是加法；
• 单位元是 $0$；
• $a$ 的逆元是 $-a$。

非零有理数在乘法下构成群：

• 单位元是 $1$；
• $a$ 的逆元是 $1/a$。

自然数在加法下不是群，因为正整数的加法逆元通常不属于自然数集合。

---

12 阿贝尔群

若群中的运算还满足交换律，则称其为阿贝尔群或交换群。

整数加法、实数加法、按位异或都构成阿贝尔群。

矩阵乘法一般不满足交换律，因此可逆矩阵在乘法下构成群，但通常不是阿贝尔群。

---

13 结构之间的关系

这些结构逐步增加条件：

$$\text{半群} +\text{单位元} = \text{幺半群},$$

$$\text{幺半群} +\text{每个元素都有逆元} = \text{群},$$

$$\text{群} +\text{交换律} = \text{阿贝尔群}.$$

算法中不应要求超过实际需要的性质。

例如：

• 快速幂只需要结合律与单位元；
• 线段树通常只需要幺半群；
• 前缀差分需要逆元；
• 稀疏表重叠查询还需要幂等性。

---

14 常见运算结构

14.1 加法

整数加法满足封闭性、结合律、交换律，单位元为 $0$，每个整数 $a$ 的逆元为 $-a$。

因此 $(\mathbb Z,+)$ 是阿贝尔群。

---

14.2 最小值

在扩展实数集合 $\mathbb R\cup\{+\infty\}$ 上，$\min$ 满足结合律、交换律和幂等性，单位元为 $+\infty$。

但通常不存在逆元。已知 $\min(a,b)$ 与 $a$，一般不能恢复 $b$。

因此最小值结构是交换幺半群，但不是群。

---

14.3 按位异或

整数按位异或满足结合律、交换律，单位元为 $0$。

每个元素都是自己的逆元，因为 $a\oplus a=0$。

因此按位异或构成阿贝尔群。

这解释了异或前缀为什么可以像普通前缀和一样求区间异或。

---

14.4 字符串拼接

字符串拼接满足结合律，单位元为空串，但不满足交换律，也通常没有逆元。

因此字符串在拼接下构成幺半群。

---

14.5 矩阵乘法

固定大小方阵的乘法满足结合律，单位元为单位矩阵，但通常不满足交换律。

只有可逆矩阵才有逆元。

所有方阵在乘法下构成幺半群；所有可逆方阵在乘法下构成群。

---

14.6 函数复合

从集合 $S$ 到自身的映射在复合下满足结合律，单位元为恒等映射。

所有映射不一定可逆，因此构成幺半群。

所有双射在复合下构成群。

---

15 快速幂的结构本质

普通快速幂计算 $a^n$，但算法并不真正依赖“数”。

它只依赖：

• 运算满足结合律；
• 存在单位元。

设运算为 $\circ$，定义

$$a^n=\underbrace{a\circ a\circ\cdots\circ a}_{n\text{ 次}}.$$

若 $n=2k$，则 $a^n=a^k\circ a^k$。

若 $n=2k+1$，则 $a^n=a^k\circ a^k\circ a$。

因此，快速幂可以用于：

• 数值乘法；
• 矩阵乘法；
• 置换复合；
• 函数复合；
• 状态转移；
• 任意幺半群上的重复运算。

---

16 线段树的结构本质

线段树把区间分解为若干子区间，再合并子区间信息。

若节点保存的信息属于集合 $S$，合并操作为 $\circ$，则通常需要：

1. $\circ$ 对 $S$ 封闭；
2. $\circ$ 满足结合律；
3. 最好存在单位元，便于处理空区间。

因此，线段树维护的通常是幺半群。

常见例子：

• 区间和：$(\mathbb Z,+)$；
• 区间最小值：$(\mathbb R\cup\{+\infty\},\min)$；
• 区间最大子段和：维护复合信息结构，并定义满足结合律的合并；
• 区间矩阵乘积：矩阵乘法；
• 区间字符串拼接：字符串连接；
• 区间函数复合：函数复合。

---

17 前缀和、差分与群

设序列元素位于群 $(G,\circ)$ 中。

定义前缀结果

$$P_i=a_1\circ a_2\circ\cdots\circ a_i.$$

只要运算构成群，并且前缀结果始终按照原顺序组合，就可以写成

$$a_l\circ\cdots\circ a_r=P_{l-1}^{-1}\circ P_r.$$

对于非交换群，逆元必须放在左侧，不能交换 $P_{l-1}^{-1}$ 与 $P_r$ 的顺序。

普通加法前缀和与异或前缀都建立在阿贝尔群上。

最小值没有逆元，因此不能仅通过两个前缀最小值恢复区间最小值。

---

18 树状数组需要什么结构

树状数组常用于前缀聚合与单点修改。

标准树状数组通过若干二进制块组合前缀，并把单点增量合并到多个节点，因此通常要求运算满足结合律与交换律。

若还要通过两个前缀结果得到任意区间结果，则还需要可逆性。

因此：

• 前缀和、前缀异或适合直接求区间结果；
• 前缀最小值不能通过“相减”得到任意区间最小值。

---

19 带权并查集与群

普通并查集只判断两个元素是否属于同一等价类。

带权并查集还维护同一等价类内部元素之间的相对关系。

设 $w(x)$ 表示 $x$ 到父节点的相对量，相对量的合并使用群运算 $\circ$。

沿父亲链组合，可以得到 $x$ 相对于根的关系。

若已知 $x$ 相对于根的关系和 $y$ 相对于根的关系，就可以利用逆元求出 $x$ 与 $y$ 的相对关系。

常见结构包括：

• 整数加法：维护距离差、分数差；
• 模 $k$ 加法：维护循环关系；
• 按位异或：维护异或关系；
• 二维向量加法：维护相对坐标。

带权并查集依赖的核心不是“权值是整数”，而是相对关系能够复合，并且能够取逆。

---

20 最短路中的两种运算

最短路同时使用两种运算：

• 路径拼接时，长度相加；
• 多条候选路径中，选择最小值。

因此，Floyd 转移写成

$$d(i,j)=\min\bigl(d(i,j),d(i,k)+d(k,j)\bigr).$$

这里的加法负责组合路径，最小值负责选择更优方案。

这种由两种运算共同构成的结构称为半环。

对竞赛学习而言，暂时只需理解：

最短路不是只依赖加法，也不是只依赖最小值，而是依赖“路径拼接”和“候选选择”两种运算的配合。

---

21 同态

设 $(S,\circ)$ 与 $(T,*)$ 是两个运算结构。

若映射 $f:S\to T$ 满足

$$f(a\circ b)=f(a)*f(b),$$

则称 $f$ 保持运算结构，也称其为同态。

同态表示：可以先在原结构中运算再映射，也可以先映射再在新结构中运算，结果相同。

例如模 $m$ 映射满足

$$(a+b)\bmod m = \bigl((a\bmod m)+(b\bmod m)\bigr)\bmod m.$$

因此，取模保持加法结构。

算法中进行状态压缩、取模、特征提取时，经常需要判断某种映射是否保留原问题所需的运算或顺序。

---

22 如何判断一种信息能否合并

面对新的区间信息或状态信息时，可以依次询问：

1. 信息对象组成什么集合？
2. 两段信息如何合并？
3. 合并结果是否仍是同类信息？
4. 合并是否满足结合律？
5. 是否存在空信息对应的单位元？
6. 是否需要逆元恢复局部信息？
7. 运算是否交换？
8. 运算是否幂等？

这些问题比直接记忆“某算法可以维护什么”更接近算法的数学本质。

---

23 算法结构对照

算法或模型	主要依赖的结构
快速幂	结合律、单位元
线段树	幺半群
前缀和	群，常为阿贝尔群
异或前缀	阿贝尔群
稀疏表区间最值	结合律、幂等性
带权并查集	群上的相对关系
矩阵快速幂	矩阵乘法幺半群
函数跳转与倍增	函数复合幺半群
最短路	路径拼接与最优选择
状态压缩集合运算	位运算与集合代数

---

24 与后续内容的联系

• 函数复合来自 映射，并提供幺半群的基本例子；
• 模乘法群、原根与离散对数会在数论中继续展开；
• 矩阵乘法、线性变换与向量空间属于线性代数的后续内容；
• 狄利克雷卷积是数论函数上的交换幺半群运算；
• 线段树、快速幂、带权并查集和最短路只是这些代数性质在算法中的不同表现。

---

25 本章思考题

1. 判断整数减法是否满足封闭性与结合律。

2. 分别写出加法、乘法、字符串拼接和矩阵乘法的单位元。

3. 说明为什么矩阵乘法虽然不满足交换律，仍可用于快速幂。

4. 判断 $(\mathbb N,+)$ 是否构成群，并说明原因。

5. 证明按位异或下每个元素都是自己的逆元。

6. 说明为什么 $\min$ 运算通常不存在逆元。

7. 解释为什么线段树的合并运算必须满足结合律。

8. 解释为什么字符串拼接可以用线段树维护，但合并左右儿子时不能交换顺序。

9. 说明稀疏表查询最小值时为何允许两个区间重叠。

10. 说明普通前缀和可以求任意区间和，而前缀最小值不能求任意区间最小值。

11. 说明快速幂为何可以用于函数复合。

12. 尝试说明带权并查集中为什么需要逆元。

13. 在最短路问题中，指出哪一种运算负责拼接路径，哪一种运算负责选择候选答案。

14. 举出一个满足结合律但不满足交换律的算法运算。