幺半群作用

幺半群作用把抽象操作解释为对象上的状态变换。单位元保持状态不变，幺半群乘法对应连续执行操作。例如把所有状态重置为同一个值，会合并原本不同的状态；这样的操作仍可与其他操作复合，自映射便能描述它。

群作用理路群作用Group action群元素以保持单位元与乘法的方式作用于集合。是其中的可逆特例：群元素的逆元对应逆变换，所以每个作用映射都是双射。幺半群作用同时容纳这种可逆变换和重置、覆盖等操作。

字符串幺半群 $({\mathrm{\Sigma }}^{\ast },\cdot ,\epsilon )$ 可通过前缀拼接作用于字符串集合：$u\cdot x=ux$。自然数加法幺半群可通过函数迭代作用于集合：

例如在非负整数上取 $f(x)=\lfloor x/2\rfloor$，则 $f(2)=f(3)=1$，迭代会逐步合并状态；而 $f^0=\mathrm{id}$、$f^{m+n}=f^m\circ f^n$ 保证它仍满足作用公理。整个自映射幺半群 $\mathrm{End}(X)$ 则通过 $f\cdot x=f(x)$ 作用在 $X$ 上。

区间加标签形成加法幺半群，并作用于带长度的区间摘要 $(s,\ell )$：

加法和赋值可以统一写成仿射标签 $(a,b)$，表示把每个数 $x$ 改为 $ax+b$：加 $v$ 是 $(1,v)$，赋值为 $c$ 是 $(0,c)$，无操作是 $(1,0)$。按上述左作用约定，

因此先赋值为 $c$、再加 $v$，结果是赋值为 $c+v$；先加 $v$、再赋值为 $c$，结果仍是 $c$。标签乘法精确记录了这个顺序差别。

懒惰传播理路懒惰传播Lazy propagation把作用于整个节点区间的可组合更新暂存为标记，仅在必要时下传。把待处理标签组织成幺半群作用，并让标签与节点摘要的合并相容：

对于区间和，取摘要 $(s,\ell )$，合并定义为 $(s,\ell )\oplus (t,k)=(s+t,\ell +k)$。仿射标签的作用为

对合并后的摘要更新，和为 $a(s+t)+b(\ell +k)$；分别更新再合并，和为 $(as+b\ell )+(at+bk)$，两者相等。长度正是计算所需的信息：区间 $[2]$ 与 $[1,1]$ 的旧和同为 $2$，每项加 $1$ 后却分别为 $3$ 与 $4$，仅记录旧和无法区分这两种结果。

自动机按从左到右的顺序读取输入字时，可以写成状态集上的右作用：先读 $u$ 再读 $v$，对应 $q\cdot (uv)=(q\cdot u)\cdot v$。函数迭代则把非负整数时间作用在状态空间上。若状态空间还带有拓扑或线性结构，要求作用映射连续或线性，就得到相应的连续作用或线性作用。