幂等半群

把 $\ast$ 看成合并信息，幂等性表示一份已经合并好的信息紧接着再来一遍，结果不变。取最小值、取最大值、集合并都符合这个图像；求和则把第二次到来的数继续计入。

“重复同一块可以消去”没有允许把任意重复符号隔空删除。一般 band 只保证 $vv=v$，不保证 $xyx=xy$，更不保证 $xy=yx$。因此在不交换的情况下，元素次序以及重复块是否紧邻都必须保留。

交换与非交换的实例 ​

任意全序集合上的 $min$、$max$ 都是交换幂等运算。对固定集合 $X$，幂集 $\mathcal{P}(X)$ 在并或交下也是幂等半群；若只取任意集合族，还必须确认该族对所选运算封闭。正整数的 $gcd$ 同样满足结合性和 $gcd(a,a)=a$。

左零半群定义 $x\ast y=x$：两种括号都返回最左元素，所以结合，平方也返回自身；不同元素一般不交换。右零半群 $x\ast y=y$ 对称地返回最右元素。这些例子说明 band 的范围严格大于半格公理库半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。。

矩形 band 更能显示次序的作用。取非空集合 $I,J$，在 $I\times J$ 上定义

三个元素相乘时，两种括号都保留第一个元素的首坐标和最后一个元素的末坐标，所以满足结合律；同一元素相乘不变。令 $a=(0,0)$、$b=(1,1)$，则 $ab=(0,1)$，但 $aba=(0,0)\ne ab$。因此不能把中间隔着 $b$ 的末尾 $a$ 当作重复信息直接删掉。

实现与额外代数律的边界 ​

加法半群一般不幂等，因为 $x+x$ 通常不等于 $x$。若直接合并重叠区间的和，交集就被重复计入。另一方面，浮点 min 含 NaN、带符号零或特殊比较规则时，不能仅凭函数名就假定结合律等代数律成立；需要按实现的实际返回语义核对。

若 band 还是群，则它只能是平凡群：对 $x^2=x$ 消去一个 $x$，得到 $x=e$。幂等聚合通常没有可以还原输入的群逆元，这也解释了为何不能照搬前缀和相减的查询公式。

若运算还交换，band 就是半格公理库半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。。以交型约定定义 $x\le y$ 当且仅当 $x\ast y=x$，幂等性给出自反性，交换律给出反对称性，结合律给出传递性。例如 $\ast =min$ 时恢复原来的全序。没有交换律时，这个简单公式未必给出偏序；左正规 band、矩形 band 等类别需要另外指定恒等式。

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

重叠块 $V$ 在拼接后连续出现，才可以直接用幂等性；这里不需要交换律。若两块完全相同，公式简化为 $V\ast V=V$。当某侧没有额外前缀或后缀时直接省略该块，而不是假定半群有空乘积或单位元。

例如数组 $[8,3,6,2,7]$ 的最小值查询，可合并长度为 $4$ 的首块和末块：两块的最小值均为 $2$，再取一次最小值得 $2$。同样两块若求和会得 $19+18=37$，真实总和却为 $26$；差出的 $11=3+6+2$ 正是重叠区间之和。