「Note」Group Theory

权当一乐。

群

称集合 $G$ 和作用于 $G$ 的二元运算 $\circ$ 为一个群，记为 $(G,\circ )$。
满足下面四个性质

1. 封闭性

   $a,b\in \mathbb{G},a\circ b\in \mathbb{G}$

2. 结合律

   $a,b,c\in \mathbb{G},(a\circ b)\circ c=a\circ (b\circ c)$

3. 幺元

   $\mathrm{\exists }!e\in \mathbb{G},\mathrm{\forall }a\in \mathbb{G},e\circ a=a$

   唯一性证明，若存在两个不相等的幺元 $e_1,e_2$，则 $e_1\circ e_2=e_1=e_2$，与 $e_1\ne e_2$ 矛盾。

4. 逆元

   $\mathrm{\forall }a\in \mathbb{G},\mathrm{\exists }!a^{-1},a^{-1}\circ a=e$

在应用上来说，树状数组维护的元素和运算必须满足群的性质，因为 $max,min$ 没有逆元，所以维护不了。

其他群

半群

若一个群 $\mathbb{G}$ 只满足封闭性和结合律，则称 $\mathbb{G}$ 是半群。

幺半群

若一个群 $\mathbb{G}$ 只满足封闭性、结合律和幺元，则称 $\mathbb{G}$ 是幺半群。

交换半群

若一个群 $\mathbb{G}$ 只满足封闭性和结合律，并且定义在上面的运算 $\circ$ 满足交换律，则称 $\mathbb{G}$ 是半群。

交换幺半群

若一个群 $\mathbb{G}$ 只满足封闭性、结合律和幺元，并且定义在上面的运算 $\circ$ 满足交换律，则称 $\mathbb{G}$ 是半群。

双半群模型

约定 $2^{I_0}$ 表示 $I_0$ 的幂集。
给定初始集合 $I_0$，一个有限集合 $I\subset I_0$，询问集合 $Q\subset 2^{I_0},s.t.I_0\in Q$，交换半群 $(D,+)$，半群 $(M,\ast )$，并且 $D\ast M\to D$，$\ast$ 对 $+$ 有分配律。
初始权值 $d_0:I\to D$。
按序执行 $m$ 个操作，操作为查询和修改，第 $i$ 个操作被定义为

1. 范围修改，给定 $q_t\in Q,f_t\in M$，定义若 $x\in q_t$，则 $d_t(x)=d_{t-1}(x)\ast f_t$，否则 $d_t(x)=d_{t-1}(x)$。
2. 范围查询，给定 $q_t\in Q$，定义 $d_t(x)=d_{t-1}(x)$，对于所有的 $x\in I$，答案为 $\sum _x{d}_t(x)$。

用 $n=\mid I\mid$ 表示初始权重的个数，用 $m$ 表示操作数。

一个满足了上述所有约束的模型被称之为双半群模型，因为方便于线段树等结构维护，维护的信息一定需要满足半群性质。解决问题的途径便是去设计 $D,M$ 去满足上述条件。