信息合并：where 结合律 from？

· · 算法·理论

在构造历史和相关问题的信息合并时，我们通常会发现已构造信息的合并不够封闭，所以我们增加新的信息直到它封闭。

而对于另一类问题，我们有可能会发现：信息是可以合并的，但是这玩意没有结合律，我们就无法用已有的强大数据结构来维护了。

本文论述了一个策略：我们不应在思考信息合并相关问题时做出“某信息的合并没有结合律”这样的武断。

信息是否具有结合律，与合并的形式密切相关，或者说，我们把原始信息针对合并这个问题进行了一定的优秀包装，使其拥有了结合律。

如果我们只盯着原始信息是否具有结合律，就极易走入歧途，从而可能“剪枝”掉某个问题的正确做法。

下面以两个例子抛砖引玉。

例1：叉积

在 2024/11/29 的 Universal OJ 用户群聊天记录中，有人提出了一个问题：给出若干个三维向量，单点修改，多次区间查询 v_l\times (v_{l+1}\times(\cdots\times (v_{r-1}\times v_r)))，其中 (x,y,z)_1\times (x,y,z)_2=(y_1z_2-y_2z_1,z_1x_2-z_2x_1,x_1y_2-x_2y_1)。

容易验证叉积没有结合律。

但我们发现，u\times v 可以看作一个向量对另一个向量的线性变换，所以我们当然可以将其写成矩阵的形式，设 M(a) 是满足 a\times b=M(a)b 的矩阵，则我们直接求出 \prod_{i=l}^{r-1}M(v_i)\times v_r 即可。

从另一个角度看，如果我们算 a\times(b\times c) 时先算出 a\times b，这是错误地把 a,b 看成和 c 等同的地位了，当计算方向是从右往左时，我们应该将 b\times c 看作“b 对 c 的操作”，而我们要做的事更像是 操作之间的合并，而非所谓的信息合并。

一个思考方式：操作的合并很类似于懒标记的合并。

例2：楼房重建

下文称 在楼房重建一题广泛使用的单侧递归线段树/平衡树 为楼房重建树。

我们都知道前缀最大值的个数可以记录最大值实现 \mathcal O(1) 的 push_back，但是“该信息并没有结合律”。

通俗的讲我们有 struct node{int mx,sum;} 和 node operator+(node a,int b) 之后，无法实现 node operator+(node a,node b)，这是大多数信息无法合并的困局所在。

同样的，我们考虑将 a(\text{node})+b(\text{int}) 看作 b 对 a 的操作，则我们要考虑的是 操作之间的合并。

不难发现，对于一连串的操作我们也只关心其前缀最大值，我们需要支持对操作序列进行二分，求出后缀（有效部分）的和，但我们不方便带着一坨序列移动，所以我们利用可持久化树存下这个过程即可完成信息的合并。

我们自然地推导出了楼房重建的 树套可持久化平衡树 的做法。