浅谈双半群模型

鱼跃于渊 · 2024-08-11 17:13:16 · 算法·理论

1. 前置

我们在学习群论时，会遇到以下概念：

• 半群：
  给定一个集合 U 以及一个集合 U 二元运算 \times 满足 U \times U \rightarrow U。
  对于此运算满足结合律，即 \forall a,b,c \in U,(a\times b)\times c=a\times (b\times c)。

• 幺半群：
  给定一个集合 U 以及一个集合 U 上的二元运算满足 U\times U \rightarrow U。
  对于此运算满足结合律，即 \forall a,b,c \in U,(a\times b)\times c=a\times (b\times c)。
  同时满足幺元（单位元）存在使得 \forall a,\epsilon \in U,a\times \epsilon = \epsilon \times a=a。

• 交换半群：
  给定一个集合 U 以及一个集合 U 二元运算 \times 满足 U \times U \rightarrow U。
  对于此运算满足结合律，即 \forall a,b,c \in U,(a\times b)\times c=a\times (b\times c)。
  对于此运算满足交换律，即 \forall a,b \in U,a\times b=b\times a。

这些概念很重要，请读者完全理解后再往下看。

2. 双半群模型

2.1. 定义

下面这什么玩意儿以后一定要重写

给定：

• 一个半群 (D,+) 和一个幺半群 (T,\times)，满足：

1. D+D\rightarrow D
2. D \times T \rightarrow D
3. T\times T\rightarrow T
4. 结合律：\forall a\in D，b,c\in T，(a\times b)\times c=a\times(b\times c)
5. 分配律：\forall a,b \in D，c\in T，(a+b)\times c=a\times c+b\times c

• 一个初始集合 I \rightarrow D 和一个询问集合 Q \subset 2^{I}（其中 2^{I} 是集合 I 的幂集）。
• 一个函数 \mathrm{val}_t(x)，其中 x\in I。特别地，我们称 \mathrm{val}_0(x) 为 x 的初始权值。

我们用 n=\lvert I \rvert 表示初始权值的个数，用 m 表示范围修改查询问题的操作数。
按顺序执行 m 个操作，每个操作是一个修改或者查询操作。
第 t 个操作定义为：

1. 范围修改：给出 q_t \in Q 和 f_t \in T，定义 \mathrm{val}_t(x)=\begin{cases} \mathrm{val}_{t-1}(x)\times f_t &\text{if } x\in q_t \\ \mathrm{val}_{t-1}(x) &\text{if } x\notin q_t \end{cases}。
2. 范围查询：给出 q_t \in Q，定义 \mathrm{val}_t(x)=\mathrm{val}_{t-1}，答案为 \sum_{x\in q_t} \mathrm{val}_{t}(x)。

如果两个群满足开头的条件，我们称其构成双半群结构。
如果一个问题满足上述条件，我们称这样的问题为双半群模型。

2.2. 具体体现

上一节给出来的模型是从纯数学的角度出发，你可以发现这玩意儿相当的抽象，不太好理解。
事实上它在算法竞赛中通常隐藏在分治维护区间信息后面出现，再具体一点它就是各种线段树，平衡树所扎根的大地（极特殊的除外）。
聪明的读者就要问了：这个模型怎么跟这堆树扯上关系的呢？
下文我们就以线段树为例，把它的各个细胞组织拆开来看看。

首先信息肯定是线段树不可或缺的一部分（没有信息我写它干嘛），它无疑可以被抽象成一个集合 D。
我们定义一个二元运算符 + 表示两个信息的合并，可以发现这些性质：

1. 显然两个信息合并后还是信息，并不会变成什么息信，即 D + D \rightarrow D。
2. 线段树上合并信息的先后顺序是无所谓的，即满足结合律 \forall a,b,c \in D，a+(b+c)=(a+b)+c。
3. 有没有交换律 \forall a,b \in D，a+b=b+a 呢？我们发现不一定，在维护区间和时显然有，但是在维护最大子段和时又没有了，所以信息不一定满足交换律。

聪明的读者肯定会发现，这不就是我们一开头提到的半群和交换半群吗？
所以我们可以得出一个结论：线段树上的信息所属的集合 D 加上合并操作 + 后，至少也是一个半群，在特殊情况下是一个交换半群。

我们在做题时还会在线段树上打上标记，如法炮制，将它也抽象成一个集合 T。
我们定义一个二元运算符 \times 表示两个标记的复合，可以发现这些性质：

1. 显然两个标记复合后还是标记，并不会变成什么记标，即 T \times T \rightarrow T，我们也可以称标记对复合封闭。
2. 线段树上标记复合的先后顺序是无所谓的，即满足结合律 \forall a,b,c \in T，a\times(b\times c)=(a\times b)\times c。
3. 如果我们什么都没做，那么肯定会出现空标记，我们把空标记记作 \epsilon，则满足 \forall a\in T， \epsilon \times a = a \times \epsilon = a。

聪明的读者肯定会发现，这不就是我们一开头提到的幺半群吗？
所以我们又可以得出一个结论：线段树上的标记所属的集合 T 加上复合操作 \times 后，是一个幺半群。

我们想想半群 D 和幺半群 T 之间有什么关系，可以发现这些性质：

1. 我们打上的标记最终会作用到信息上，而信息被影响后还是信息，即 D \times T \rightarrow D。
2. 我们发现，一个信息先应用一个标记再应用另一个标记，结果和应用两个标记的复合一致，即结合律 \forall a\in D，b,c\in T，(a\times b)\times c=a\times(b\times c)。
3. 我们发现，标记下传后，当前结点的信息等于两个子树的信息的合并，即 \times 对 + 有分配律：\forall a,b \in D，c\in T，(a+b)\times c=a\times c+b\times c。

聪明的读者肯定会发现，这不就是我们一开头提到的双半群结构吗？
所以我们还可以得出一个结论，线段树上的信息所属的半群 (D,+) 和标记所属的幺半群 (T,\times) 构成一个双半群结构。
而如果我们再把题目中要求的区间修改区间查询加入其中，它就变成了我们熟知的双半群模型。

2.3. 原理

说了这么多，也该进入正题——通过双半群模型构造我们想要的数据结构了，下面依然还是以线段树为例。

2.3.1. 暴力进行时

有一个问题，要求支持区间加、区间乘、区间和，如果我们偷懒，想到线段树可以维护矩阵，写出如下式子：

可以发现这个写法很笨，明明只要两个变量维护的东西我们却用了四个变量。

但还有没有更笨的方法呢？我们考虑一个十分抽象的问题：

1. 维护一个序列，序列里每个元素是个抽象的数据，其类型 M 的具体实现你是不知道的。
2. 要求支持操作：给你一个黑盒函数 f(M) 使得 f(M) \rightarrow M，以及一个代表一段区间的数组，要求你作用这个函数到数组内的每个元素。
3. 支持查询：给你一个黑盒函数 ans(M) 使得 ans(M)\rightarrow M，以及一个代表一段区间的数组，要求你作用这个函数到数组内的每个元素，然后得出结果。

可以发现，所有区间修改区间查询的线段树问题都可以抽象到这个问题、我们考虑一下这个问题怎么用线段树做。
因为我们对这些东西一无所知，所以我们无法压缩信息和标记，只有唯一的方法：

• 一个标记就是一个 f(M)\rightarrow M 的函数，我们不保证这个函数可以 O(1) 执行。因为如果传进来一个黑盒函数 f_1，又传进来黑盒函数 f_2，那我们只能得到一个新的函数 f(x)=f_2(f_1(x))，即两个函数的复合。传入多个的话就是一层层的俄罗斯套娃（所以标记的结合叫做复合，因为它本身就是函数的复合）。
• 一个信息就是一个数组，即区间维护的信息就是区间本身。因为我们一无所知，所以完全不能提取出更细致的东西来。
• 信息的合并，就是两个数组拼起来。
• 标记的复合，就是函数的复合。
• 标记作用在信息上，就是遍历区间里的每个元素，扔到函数里拿出来，更新一遍。

因为我们没有任何的简化，所以只能采取暴力得让人发指的方法，复杂度估计是 O(n^3 \log n) 以上，不过我们的确是用线段树解决的。（笑）

我们为什么要举这个比暴力还要暴力的构造出来呢？因为这个憨憨是线段树维护区间信息的某种基础，它具有某种“万有性”。
比如说，如果 A 和 B 设计了不同的以信息 + 标记为基础的数据结构，而如果 A 所维护的东西完全可以实现 B 所维护的东西（换而言之，即使不知道具体结构，我们也可以通过 A 的信息推算出 B 的所有信息，用 A 的标记实现 B 的所有标记），那我们就可以称 A 的数据结构更强（不考虑时空复杂度）。
如果这么说，上面这个憨憨构造就比所有的以信息 + 标记为基础的数据结构都强！

2.3.2. 返璞归真

事实上，我们虽然做题时不可能用这个憨憨构造，但是我们发扬拿来主义，借鉴个一下。
具体的说，设前面那个构造的信息为 D_0=代表总区间的数组，标记为 T_0={所有 f(M) \rightarrow M 的函数}，则我们可以注意到以下事实：

• 信息 D 总是由 D_0 计算得来，显然区间的信息就是从整个区间计算而来的。
• 标记 T 总是 T_0 的一个子集（数学上过程不同结果相同的函数算同一个），显然一个标记归根结底就是一个将元素变成新元素的函数。
  从这点我们也容易发现 T 里的复合与 T_0 里的复合一致，并且 T 里的标记复合起来还应该在 T 里，即前文提到的标记对复合封闭，也可以称复合的封闭性（T \times T \rightarrow T）。
• 设从 D_0 算出 D 的函数为 g(D) \rightarrow D，这个计算应该能兼容信息合并和标记作用。 具体而言，如果 t \in T， d,d_1,d_2\in D_0，则有：
• 1. 如果知道左右区间的信息，可以合并得到大区间的信息。这就是说我们正确地合并了信息，即 $D + D \rightarrow D$。
• 2. 如果知道标记 $t$ 和之前的信息 $g(d)$，可以计算得到新的信息 $g(d \times t)$。这就是说我们正确地更新了信息，即$D \times T \rightarrow D$。

这里非平凡的事情只有：标记对复合是封闭的和上面的两个等式。
我们可以吃惊地发现：只要选定了 T\subset T_0 以及 D 和 g:D_0\rightarrow D，满足复合的封闭性以及上面两条等式，它们一定满足双半群性质。
结合律分配律什么的完全不用管，因为我们选取标记和信息的方式决定它们一定正确。
想想看，区间信息能正确合并怎么可能不结合？标记能复合怎么可能不结合？标记能正确影响区间怎么会不能分配？
而在实际实现中，我们一般不会把 T 真的实现成函数——例如在区间加、区间乘、区间和中，我们只要发现修改最后都可以被表示成形如 f(x)=ax+b 的函数，之后用一个二元组 (a,b) 来表示 f(x)=ax+b 这个函数即可。
这样一来，我们还可以得出两条等式：

1. 若 f_t 是标记 t 简化前代表的函数，则 f_t\times g(d)=g(d \times f_t)。也就是说简化后的标记作用在信息上等价于与原本的函数作用在区间上，相当于我们正确地用标记简化了原函数。

我们看到，我们最终返璞归真，回到了封闭律主宰一切的时期。

2.3.3. 实际方法

上一节已经提到构造需要满足的三个条件：

1. 如果知道左右区间的信息，可以合并得到大区间的信息（D + D \rightarrow D）。
2. 如果知道标记和之前的信息，可以计算得到新的信息（D \times T \rightarrow D）。
3. 标记对复合封闭（T \times T \rightarrow T）。

据此，我们可以得出一个构造流程：

1. 构造可行的信息 D，检验是否满足 D+D\rightarrow D，并得出转移形式。
2. 通过计算各个操作对信息 D 的影响，总结出标记 T，检验是否满足 D\times T \rightarrow D，并得出转移形式。
3. 通过计算验证标记 T 是否满足 T\times T \rightarrow T，并得出转移形式。
4. 如果出现不满足的情况，从 1 重新开始。

上述依据是什么呢？
我们从题目中最先构造出来的肯定是信息，其次由操作可以归纳出我们要的函数简化形式（标记），最后得出来的就是标记的复合了。
实际上双半群模型的强悍之处，就在于只要我们知道我们要维护的信息 D，以及我们要支持的操作，就可以推出我们需要维护的标记 M 的形式，以及合并与复合的三个式子。

3. 构造矩阵

3.1. 引入

我们在前文提到过使用矩阵的笨做法，不过笨归笨，比起暴力和那个憨憨构造来说也是一个好方法，而且有些题目也基本只能构造出矩阵来解决。
不过虽然矩阵慢是慢了点，但它有一些特殊性质。
比方说，它天然就是一个幺半群。这意味着如果我们的信息和标记都是矩阵的形式，则其天然就是一个双半群模型。
这给我们的构造带来了极大的方便（读者可以参照下面几大节对比体会）。
比方说构造 D\times T \rightarrow D 时，我们发现我们只要对于题目中的每一个操作都构造出一个矩阵就可以了。
另外只要 T 构造出来，它就天然满足 T\times T\rightarrow T，我们就不需要另外再推导转移形式了。
下面我们将会给出两个例子来详细地讨论一下。

3.2 P7453 [THUSCH2017] 大魔法师

有三个序列 a,b,c，长度均为 n。
又有 7 种操作，共 m 个，分别为：

1. 令 a_i=a_i+b_i
2. 令 b_i=b_i+c_i
3. 令 c_i=c_i+a_i
4. 令 a_i=a_i+k
5. 令 b_i=b_i\times k
6. 令 c_i=k
7. 查询 \sum_{i=l}^{r} a_i,\sum_{i=l}^{r} b_i,\sum_{i=l}^{r} c_i

我们发现这里的操作实在太多太复杂了，几乎不可能直接推导，考虑构造矩阵简化思考。
首先考虑信息，我们肯定要有 a,b,c 在里头，而且还可以发现，我们还要有一个地方来支持 a_i+k。（自行构造一下 3\times 3 的矩阵标记就知道为什么了）
也就是说我们构造出来的信息应该是

这里为了兼顾代码实现，所以使用了 4\times 4 的矩阵而不是 1\times 4 的向量。