线段树维护分治信息略解

铃悬 · 2023-02-16 22:44:13 · 个人记录

前言

今日又在 UOJ 群中看到有小友提问线段树维护信息的“双半群”性质云云，遂写此文，略解线段树。

其实与其说略解线段树，倒不如说略解区间分治信息维护，毕竟树状区间数据结构，诸如线段树，Splay，Treap等，都遵同理。

若读此文，读者需预先了解何为线段树，最好应该写过例题

维护一序列 A_i，支持区间乘，区间加，查询区间和。

或读者自认为难度仿佛的习题。不然可能难以理解本文所说的线段树结构以及实现。

本文同步发布于UOJ:_rqy的博客，是我和 _rqy 共同写作（应该有人能看出来文风的细微不同）。

标记和信息

众所周知——也或者没有那么周知，线段树通过打标记维护信息的时候，标记和信息分别要构成半群，并且之间的作用要具有分配律，此之谓“双半群”。具体地说，

线段树每个结点上有一个“标记”，其具有类型 T，或者说属于集合 T。
每个结点还有一个“信息”，其具有类型 D，或者说属于集合 D。
由于我们要合并信息，必须有一个合并函数 \operatorname{merge}(D, D) \to D。如果我们维护的是区间和，那么合并就是加法。
如果当前结点有懒标记，那么为了得出这个结点的信息（也就是所谓的 pushup 或者 update），除了要合并两个子树的信息之外，还要考虑合并之后的信息在这个懒标记应用上去之后变成什么。这就要求我们有一个“作用”函数 \operatorname{apply}(T, D) \to D。
打标记或者下传标记的时候，有可能要打标记的结点原来就有标记。这就需要我们知道两个标记先后作用之后会变成什么标记，也就是一个标记复合函数 \operatorname{compose}(T, T) \to T。如果对一个区间先打上 t_1 标记，再打上 t_2 标记，结果应该和打上 \operatorname{compose}(t_2, t_1) 标记相同。

举个例子。假设我们操作是区间乘和区间加，要维护区间和。那么：

标记 T 就形如 (a, b)，表示要把区间里每个数 x 都变成 ax+b。
信息 D 就形如 (l, s)，其中 l 表示区间长度，s 表示区间和。虽然其实这个 l 永远不会变所以不用维护，我们只是形式地这么写一下而已。
信息的合并就是简单的 \operatorname{merge}((l_1, s_1), (l_2, s_2)) = (l_1 + l_2, s_1 + s_2).
标记对信息的作用是 \operatorname{apply}((a, b), (l, s)) = (l, as + bl)。
标记的复合是 \operatorname{compose}((a_1, b_1), (a_2, b_2)) = (a_1a_2, a_1b_2 + b_1)。注意我们的符号是先作用第二个再作用第一个。

如果我们只有区间乘，那标记就是一个数表示区间乘 x，信息就是一个和 s。合并就是加法，作用和复合都是乘法。因此，我们在一般情况下，也用加法符号 + 表示合并，乘法符号 \times 或者 \ast 表示作用和复合。

上面的例子就变成

“双半群”结构

接下来我们想一想标记和信息组成的这个结构，或者说系统，具体要满足哪些条件。

首先，区间信息合并的先后顺序是无所谓的。如果有三个区间 [l, x], [x+1, y], [y+1,r], 他们对应的信息分别是 d_1, d_2, d_3, 那么总应该有 \operatorname{merge}(\operatorname{merge}(d_1, d_2), d_3) = \operatorname{merge}(d_1, \operatorname{merge}(d_2, d_3)).
或者说 (d_1 + d_2) + d_3 = d_1 + (d_2 + d_3). 也就是说信息的合并满足结合律.
标记也应该有结合律：t_1(t_2t_3) = (t_1t_2)t_3.
而且，根据我们“作用 \operatorname{compose}(t_1, t_2) 等价于先作用 t_2 再作用 t_1”的原则，总应该有 (t_1t_2)d = t_1(t_2d).

这也就是为什么我们规定成先 t_2 后 t_1，不然写起来顺序就乱了.
此外，我们发现，标记下传之后，当前结点的信息是不会变的。也就是说，两个子树的信息先合并再应用标记，或者先应用标记再合并，得到的应该是一样的。这样就是说 t(d_1 + d_2) = td_1 + td_2.
最后，当我们什么都没做的时候，每个结点上的标记都是“空的”，表示什么都不做。我们把这个标记记作 \epsilon。它满足 \epsilon d = d（确实是什么都不做）。
作为一点显然的补充，我们有 \epsilon t = t \epsilon = t。毕竟 \epsilon 就是什么都不做。

数学中，我们把配备了一个二元运算且具有结合律的结构叫做半群。那么可以发现

所有信息，加上合并操作，构成了一个半群。
所有标记，加上复合操作，构成了一个半群。而且它有一个“单位元” \epsilon，所以是幺半群（单位元也叫幺元，所以幺半群其实就是字面意思，带幺的半群）。
除此之外，标记还会作用在信息上。按数学的话讲，这叫做幺半群作用。

这看上去非常的复杂！有没有简单的办法呢？比如说，我懒得想标记和信息是什么形式了，有没有暴力做法呢！

答案是：当然有！虽然很笨蛋！

“万有”双半群

想象一下，有一个问题，要求区间加和区间乘。但是我偷懒，发现按矩阵的方式，
\begin{bmatrix} a & b \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ 1\end{bmatrix} = \begin{bmatrix} ax+b \\ 1\end{bmatrix}.
我想起大佬教给我：线段树可以维护矩阵乘法！

于是我每个标记都是一个 2 \times 2 的矩阵，信息是 2 \times 1 的向量。

可以发现这个例子里，“我”很笨蛋，明明两个数就能维护的标记，我却要用四个数维护。但是虽然笨蛋，却也找到了办法。

有没有“最笨蛋”的办法呢！笨蛋到不需要思考的办法，不需要大佬教矩阵乘法的办法。

答案是确实有。我们考虑这样的抽象的问题：

维护一个序列，序列里每个元素是个抽象的数据，具有你不知道具体实现的类型 M.
要求支持操作：给你一个黑盒函数 M \to M, 以及一个区间，要求你把区间里每个元素都作用上这个函数。
支持查询：给你一个黑盒函数 \operatorname{Array}(M) \to M, 以及一个区间，要求你把这个区间提取出来传到这个函数里，然后递出去结果。这里 Array 是数组，C++ 选手可以理解为 vector<M>。

可以发现，所有区间修改区间查询的线段树问题都可以规约到这个问题！（废话.jpg）那么这个问题，怎么使用线段树做呢？（虽然我知道你想说线段树不如暴力）

显然我们没有任何办法压缩标记和信息，毕竟我们对他们一无所知。那么唯一的办法就是：

一个标记就是一个 M \to M 的函数——不保证这个函数可以 O(1) 执行。因为如果传进来一个黑盒函数 f_1, 又传进来黑盒函数 f_2，那我们只能得到一个新的函数你也可以干脆认为一个标记就是一个 vector，里面装着很多黑盒函数，表示要依次执行这些函数。
一个信息...就是一个 \operatorname{Array}(M). 没错，区间维护的信息就是区间本身。因为我们对 M 一无所知，完全不能提取出更细致的东西了。很笨蛋！
信息的合并...就是俩 Array 拼起来。
标记的复合...就是函数复合。
标记作用在信息上...就是遍历 Array 里每个元素，扔到函数里拿出来，组成新的 Array。

很笨蛋！由于我们没有任何简化，执行一个函数其实是执行输入的一系列函数的复合，有可能一次就是 O(n) 的。所以只是做一次“标记作用在信息上”，就可能 O(n^2) 了！最终复杂度可能是 O(n^3)，不过我们确实是用线段树解决的，不是吗（

为什么要提到这个笨蛋的构造呢？ 事实上，这个无比憨憨的构造反而是线段树维护区间信息的某种基础，它具有某种“万有性”。

比如说，如果小明和小红分别设计了一套标记+信息的结构，而小明维护的信息以及标记完全可以实现小红的所有信息和标记（也就是说，即使不知道子树长什么样，我们也可以完全通过小明的信息，推算出小红的信息；而且小红的所有标记都可以用小明的标记实现，反过来却不一定），那我们可以认为小明的结构更强。如果这么说，上面这个笨蛋构造就比所有信息+标记结构都强！

但是~~古尔丹~~，代价是什么呢？代价当然就是比暴力还要可怜的复杂度。~~强度也高，复杂度也高，全面吊打~~

这也是为什么本文把标记的结合叫做复合——它本就是函数的复合。

事实上，这种“万有性”可以启发我们得出以下的事实：

双半群重要吗？

显然我们不可能用上面那个笨蛋构造。那么怎么办呢？

虽然不可能用，但是可以借鉴。具体地说，设前面那个构造的标记为 T_0\ (=\{\text{所有}\ M \to M\ \text{的函数}\})，信息为 D_0\ (=\operatorname{Array}(M))。

那么一般情况下：

标记 T 总是 T_0 的一个子集。（我们只考虑数学上的函数。也就是说算法不同结果相同的函数也算同一个）这是废话，因为一个标记总应该是把元素变成新的元素的函数。
而且当然，T 里的复合跟 T_0 里的复合是同样的；并且 T 里的标记复合起来还应该在 T 里。也就是复合的封闭性。
信息 D 总是从 D_0 计算出来的。这也是废话，区间信息可不就是从整个区间算出来的吗。
设从 D_0 算出 D 的函数为 c \colon D_0 \to D. 这个计算应该是与信息合并、标记作用是兼容的。具体地说，若 t \in T, d, d_1, d_2 \in D_0, 那么

这里非平凡的事情只有三件：

第一，标记对复合是封闭的。第二第三，上面的这两个等式。

并且只要选定了 T \subset T_0 以及 D 和 c \colon D_0 \to D，满足复合的封闭性以及上面两条等式，它们一定满足双半群性质。

结合律分配律完全不用管：因为我们选取标记和信息的方式决定它们一定正确（函数复合怎么可能不结合？区间信息只要能正确合并，怎么可能不结合？）。

我们甚至会看到，这两条等式其实是平凡的：

在具体实现中，我们一般不会把 T 真的实现为函数类型——例如区间加区间乘，我们发现只需要处理形如 f(x) = ax+b 的函数，之后就可以记录 (a, b) 来表示 f(x) = ax+b 这个函数。这样，我们就还要加两条等式：

若 f_t 是标记 t 所代表的函数，那么 tc(d) = c(f_td)。简化的标记作用在信息上总等价于原本的函数作用在区间上之后的信息。相当于说我们用简化标记代表的函数方式代表对了。

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

到底如何构造标记与信息？

我们看到标记会影响信息，但是信息不能反过来影响标记。

既然如此，我们先看看标记要怎么构造。

标记

只看标记，唯一重要的事情就是复合的封闭性。

最小的满足封闭性的标记集合是什么？无非就是输入要求的若干修改的复合。

例如此题：

维护三个整数序列 A_i, B_i, S_i，支持区间 A_i += x，区间 B_i += x，区间 S_i += x \times A_i \times B_i。

我们发现其实 A_i, B_i, S_i 是绑定的。所以与其说维护三个序列，不如说维护一个序列，只不过每个元素是个三元组 (a, b, s)。

如果我们以任意顺序执行任意多次这三种修改，都是全局修改，最后我们打在线段树根结点的标记应该怎么样？

换句话说，很多形如 f((a, b, s)) = (a + x, b, s) 或者 f((a, b, s)) = (a, b + x, s) 或者 f((a, b, s) = (a, b, s + xab) 的函数复合起来，会得到什么样的函数？

这个过程，应当手算，从 (a,b,s) 出发，随便扔一些修改上去，直到你发现形式固定下来位置。这道题中，我们发现怎么搞也跳不出 f((a, b, s)) = (a + x, b + y, s + z + ua + vb + wab) 这样的形式。

因此我们可以记一个六元组 (x, y, z, u, v, w) 表示上面这个函数，至于复合就只需把两个形如上面这样的函数复合起来看看新的六个系数分别是多少。

信息

有了标记，接下来我们就可以构造信息。

首先我们要求，信息能涵盖我们的询问。

之后就是那两条等式。我们可以读作：必须能够用左右区间的信息合并出大区间的信息，必须能够从原本的信息计算出打标记后的信息。简单说就是信息可以合并、信息可以在打标记时更新。

先要求信息可以合并。例如说经典例题

维护序列，支持单点修改，维护区间最大子段和。

既然是单点修改那就没有标记，只需要想信息。为了知道一个区间的最大子段和？我们需要知道左右区间的什么信息？不难想到，除了最大子段和之外，还要知道左区间的最大后缀和，右区间的最大前缀和。所以我们要维护这两个。

这就完了么？还没有呢：注意信息合并起来形式不能变，所以子区间要维护最大前后缀和，大区间也维护。那么这需要子区间什么信息？可以发现还需要知道整个区间的总和。

最后检查一下，这样的信息确实是可以完全合并起来的。我们就大功告成。

但是有时候还会有标记。我们就还要问：为了知道打标记之后的信息，我们需要知道打标记前的什么信息？

例如上述问题中，如果我们要求支持区间加，那么埋头苦算一番，就知道要知道区间加后的最大子段和，需要知道之前的 (子段长, 子段和) 构成的凸包。

别忘了回去看看信息合并：为了知道大区间的凸包，需要知道小区间的什么？可以发现需要知道小区间的前缀和凸包，后缀和凸包，以及子段和凸包，还有整个区间和。而且这个可以完全合并了。

还得再回来：要知道打标记之后的这一大堆信息，需要知道打标记前的什么？幸运的是这次我们发现不用增加信息了，所以可以停下迭代了。

当然线段树维护这东西复杂度就爆炸了，我们这里只是借这个例子陈述这样一种模型。

结语

无论什么理论中，总有这样一个原理：越具体的事物就具有越多的性质。具体就性质多，那么抽象自然就性质少。性质少也就决定了方法少——想想那个我们一无所知的黑盒类型，黑盒修改黑盒查询，最优的算法就只是暴力。

我们这里描述的理论虽然颇费口舌，但总归是抽象的。具体的问题总要具体的分析，本文难以涵盖的细节和例外情况也大有所在。例如有些时候，标记的下传是取决于信息的。更何况，线段树也只是树状数据结构之一，后者又只是所有数据结构中的一类；不维护序列的数据结构也有所存在。但是希望本文的方法和思想，可以给读者以启发。

本文作为笔者的第一篇数据结构文章，此前打过两千字草稿，总觉不得其精髓。今日与 UOJ 友人交流一番后文思泉涌，散步时已胸有成竹，不知不觉已写到深夜。遥想当年竞赛时期的努力颇有感慨，因此也希望本文能作为各位读者前行路上的微弱灯火，助诸位在人生道路上更进一步。