「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. 幺元

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

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

4. 逆元

   $\forall a \in \mathbb{G}, \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, *)$，并且 $D * M \rightarrow D$，$*$ 对 $+$ 有分配律。
初始权值 $d_0: I \rightarrow D$。
按序执行 $m$ 个操作，操作为查询和修改，第 $i$ 个操作被定义为

1. 范围修改，给定 $q_t \in Q, f_t \in M$，定义若 $x \in q_t$，则 $d_t(x) = d_{t - 1}(x) * 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$ 去满足上述条件。