幂等半群

形式陈述 ​

幂等半群（band）是满足

$$x\ast x=x(\mathrm{\forall }x\in S)$$

的半群公理库半群Semigroup带有结合二元运算的集合。 $(S,\ast )$。因此运算同时具有封闭性、结合律和逐元素幂等性，但不必交换，也不必有单位元。

幂等性作用于半群中的每个元素。若 $v=a_1\ast \cdots \ast a_k$ 是一个区块的聚合值，则 $v\ast v=v$；这正是某些重叠区间算法能够消去整块重复的代数原因。

直觉 ​

普通半群允许重新加括号，幂等半群进一步允许一个已经聚合好的信息块重复出现而不改变结果。它适合“重复证据不增加信息”的聚合，如取最小、取最大、集合并。

幂等不等于交换。重复同一个整体可消去，并不意味着两个不同操作可以换序。把这两条性质混在一起，会把算法真正需要的最小代数条件写得过强。

例子与边界 ​

任意全序集合上的 $min$ 或 $max$ 构成交换幂等半群。集合族在并或交下也是如此。正整数在 $gcd$ 下构成交换幂等半群，因为 $gcd(x,x)=x$。

非交换例子是左零半群 $x\ast y=x$。它满足结合律与 $x\ast x=x$，但通常 $x\ast y\ne y\ast x$。右零半群 $x\ast y=y$ 也同样。它们说明 band 严格大于半格公理库半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。。

加法半群一般不幂等：$x+x\ne x$。因此把两个重叠区间和直接相加会重复计算交集。浮点 min 若含 NaN、带符号零或非标准比较语义，还需先确认实现层运算是否真正满足所声明的代数律。

推论与应用 ​

若运算还交换，幂等半群就是半格公理库半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。，可由运算诱导偏序。没有交换律时仍可研究左正规 band、矩形 band 等更细类别，但这些额外恒等式不由幂等性自动推出。

Sparse Table公理库稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。 的两个重叠块技巧只需结合性和幂等性：若左块聚合为 $U\ast V$、右块为 $V\ast W$，则

$$(U\ast V)\ast (V\ast W)=U\ast (V\ast V)\ast W=U\ast V\ast W.$$

这里重叠部分 $V$ 以相同顺序连续出现，因此不需要交换律；这比常见的“必须是半格运算”说法更精确。

参考资料

• John M. Howie, Fundamentals of Semigroup Theory, Oxford University Press, 1995, Chapters 1 and 4.
• A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Vol. I, American Mathematical Society, 1961.
• J. M. Howie, “An Introduction to Semigroup Theory,” Academic Press, 1976, sections on bands.