幂等半群

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

这条规则作用于相邻的同一块：$vv$ 可以化为 $v$。若两个 $x$ 中间夹着 $y$，得到的 $xyx$ 则可能与 $xy$ 不同，因为中间的合并改变了结果。下面的矩形 band 会具体展示这一点。

交换与非交换的实例 ​

任意非空全序集合上的 $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\ast y=(x+y)/2$ 满足 $x\ast x=x$，却不结合：$(0\ast 0)\ast 4=2$，而 $0\ast (0\ast 4)=1$。它因此无法用半群的括号规则来聚合多个输入。普通加法则相反：它结合，但 $x+x=2x$，会把重叠区间重复计入。

若 band 还是群，则它只能是平凡群：对 $x^2=x$ 消去一个 $x$，得到 $x=e$。最小值、集合并等非平凡幂等聚合会合并不同输入的信息，因此使用重叠块查询，而不依靠前缀和式的群逆运算。

若运算还交换，band 就是半格理路半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。。以交型约定定义 $x\le y$ 当且仅当 $x\ast y=x$，所得关系是偏序理路偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。：幂等性给出自反性，交换律给出反对称性，结合律给出传递性。例如 $\ast =min$ 时恢复原来的全序。在含两个以上元素的左零半群中，这一关系却让任意两个元素都互相“小于等于”，因而失去反对称性。

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$ 正是重叠区间之和。