对动态 DP 和全局平衡二叉树的一点补充解释

2023-08-29 17:26 由 changle_cyx 发表于 #其他

说明：最近在帮高中竞赛教练写讲义，这是本人对讲义中动态 DP 内容的补充解释（因为主要是对知识点的理解，不太容易用通用的语言表述，也不适合作为讲义内容供读者阅读，所以用的是补充注释的形式）。写的比较抽象也比较初等，仅供意会。

1. 为什么用矩阵表示转移

我们先从一般的角度，用映射的语言来表示 DP。以序列 DP 为例，假设 \(\{ \mathrm{dp}_{i}\}\) 是 DP 值数组，\(\left\{ a_{i} \right\}\) 是每个位置的信息（说明：DP 值数组可以是 \((f_i,g_i)\) 这样不止一个的；每个位置的信息 \(a_i\) 也不一定代表权值，也可以是 \((i,a_i,b_i,c_i,...)\) 这样更加复杂的信息）。

那么通常来说，一个 DP 的转移过程可以表示为如下关系式：

\[\left( \mathrm{dp}_{n},\ \mathrm{dp}_{n - 1},\ldots,\mathrm{dp}_{n - k + 1} \right) = T_{a_{n}}(\mathrm{dp}_{n - 1},\ \mathrm{dp}_{n - 2},\ldots,\mathrm{dp}_{n - k}) \]

其中 \(T_{a_{n}}\) 是一个由 \(a_{n}\) 决定的映射，表示用 \((\mathrm{dp}_{n - 1},\ \mathrm{dp}_{n - 2},\ldots,\mathrm{dp}_{n - k})\) 这些 DP 值能够确定 \(\mathrm{dp}_{n}\) 的值（将函数值写成 \(k\) 元组只是为了方便下文书写）。

这里 \(k\) 表示 \(\mathrm{dp}_{n}\) 由前面 \(k\) 个已知的 DP 值确定。在例题 1（区间最大子段和）中 \(k = 1\)，即表示 \(\mathrm{dp}_{n}\) 只与 \(\mathrm{dp}_{n - 1}\) 有关，在斐波那契数列的递推关系中就可以认为是 \(k = 2\)。那么我们容易知道：

\[\begin{aligned}\left( \mathrm{dp}_{n},\ \mathrm{dp}_{n - 1},\ldots,\mathrm{dp}_{n - k + 1} \right) &= T_{a_{n}}\left( T_{a_{n - 1}}\left( \ldots\left( T_{a_{k + 1}}\left( \mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1} \right) \right) \right) \right) \\&= \left( T_{a_{n}} \circ T_{a_{n - 1}} \circ \cdots \circ T_{a_{k + 1}} \right)(\mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1})\end{aligned}\]

这里 \(\circ\) 表示映射的复合运算，而 \(\left( \mathrm{dp}_{k},\mathrm{dp}_{k - 1},\ldots,\mathrm{dp}_{1} \right)\) 可以认为就是 DP 的初值。

有时，为了快速计算最终的答案 \(\mathrm{dp}_{n}\)，我们会利用映射的特殊性质，试图求出 \(T_{a_{n}} \circ T_{a_{n - 1}} \circ \cdots \circ T_{a_{k + 1}}\) 的表达式，进而计算。以斐波那契数列的递推关系为例，

\[\begin{bmatrix} {\mathrm{dp}}_{n} \\ {\mathrm{dp}}_{n - 1} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix}\]

此时就相当于 \(T\left( \begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix} \right) = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\begin{bmatrix} \mathrm{dp}_{n - 1} \\ {\mathrm{dp}}_{n - 2} \\ \end{bmatrix} = \begin{bmatrix} {\mathrm{dp}}_{n} \\ {\mathrm{dp}}_{n - 1} \\ \end{bmatrix}\)。

更一般地，所有齐次线性递推转移方程其实都可以将DP转移表示为一个矩阵乘法，此时求映射复合就相当于求矩阵乘积，这就是矩阵快速幂优化线性递推的一种解释。

对于更常见的最优化DP，有时也可以用类似的思路处理。比如例1的区间最大子段和，转移就可以描述为：

\[T_{a_{n}}\begin{pmatrix} f_{n - 1} \\ g_{n - 1} \\ \end{pmatrix} = \begin{pmatrix} \max\left\{ f_{n - 1} + a_{n},a_{n} \right\} \\ \max\left\{ f_{n - 1} + a_{n},a_{n},g_{n - 1} \right\} \\ \end{pmatrix} = \begin{pmatrix} f_{n} \\ g_{n} \\ \end{pmatrix}\]

用 \(\left( \max, + \right)\) 广义矩阵乘法，可以将其写为矩阵乘法的形式，此处不再重复。写为矩阵乘法后，就利用矩阵乘法的结合律，进而用数据结构维护。

以上虽然都是用矩阵乘法的形式处理，但实质上，是因为这些转移对应的映射 \(\mathbf{T}\) 以及映射的复合都满足某些特殊性质，进而才能够用矩阵表示。回顾例 1 的另一种线段树做法，维护区间和、区间最大前缀和、最大后缀和、最大子段和这四个信息，其实就是在维护转移映射合并后的结果，所以它虽然没有显式出现矩阵乘法，但其实也能算作动态DP。

一般来说，如果转移对应的映射及其复合（或者说多个转移"合并"后）能够满足某些特殊性质，使其能够用少量信息表示（例如例1的四个区间信息，再例如若干次线性递推能够用多个矩阵的乘积表示），并且合并过程也比较容易，我们就能够用分治思想来对这些映射进行复合运算。体现在线性递推上，就是矩阵快速幂；如果带修改，那么用线段树就能很方便地维护一个映射变化，造成的复合运算结果的改变。

其中，能够分治计算依赖的是映射复合的结合律（这是自然成立的）。而真正需要注意的其实并非结合律，而是满足"特殊性质"映射对复合运算的"封闭性"（此处略去解释）。【所以，矩阵只是一种易于理解、易于推导的转移形式，矩阵乘法并不是本质的，分治思想才是解决问题的核心】

2. 如何将序列问题的解法迁移到树上问题

上文提到的方法只针对序列 DP，对于树上问题，我们通常是采用链分治的方式。对于一条重链，将每个结点轻儿子的信息合并到这个结点上（视作这个结点的信息），然后就可以在重链上用序列 DP 的方式处理了。

至于链分治的具体方式，就有三种常见方法（树剖+线段树；LCT；全局平衡二叉树），其中全局平衡二叉树的理论复杂度和实际表现都最优。

链分治的思想也可以迁移到更广泛的问题，例如链分治FFT解决部分计数问题、链分治闵可夫斯基和解决凸性DP问题（典例——树上最大边权k-匹配问题CFGym 102331J）。解决这些问题应用到的核心性质是——经过重链条数 / 全局平衡二叉树深度为 \(O(\log n)\)

这里补充说明一点：全局平衡二叉树实际上就是在重链剖分基础上，将“将重链分为两半”的分治方式，变成了“按照轻儿子的总 size + 1 为权重来分重链”的分治方式。而具体的维护细节（只是分治而不需要保留结构 or 需要用数据结构维护分治结构；线段树 or 平衡树；是否 leafy）和树链剖分都是没有实际区别的。

热门相关：我有一座恐怖屋本法官萌萌哒大妆今天也没变成玩偶呢拒嫁豪门，前妻太抢手