基于变换合并的树链剖分维护动态树形动规算法 | Bill Yang's Blog

基于变换合并的树链剖分维护动态树形动规算法

本文使用树链剖分维护一类动态的树形动规问题。
也可以参考immortalco的文章

我们曾经做过一类动态序列动规问题,也就是将静态的序列问题放在线段树上维护。
不妨将其推广到树上,使用树链剖分来维护动态的树形动规问题。
不妨再将其推广到仙人掌上。

重链剖分与可合并$tag$

既然是树链剖分,首先将转移方程拆分成与重儿子有关的式子和与重儿子无关的式子。

洪水的方程:

拆分为:

将$(a,b)$二元组视为一个$tag$,其满足结合律,也就是可合并:

目前遇到的$tag$出现了这样的多元组变换与矩阵变换的形式。
当然不排除还会有其他形式,只要是可合并的$tag$即可。

然后考虑使用线段树维护$tag$。

$tag$的合并

接下来我们会用到这些变量/数组:

  • $tag$:线段树维护的属性。
  • $f$:树形动规数组。
  • $restf$:轻儿子的$f$的复合。

对于每一条重链$l\rightarrow r$,我们维护一个线段树来处理其值。
线段树每个结点$[x,r]$包含一个$tag$,表示链底的虚拟儿子结点(并不实际存在,理想的作为单位元的儿子)的$f$值(在洪水题中为$0$)经过$tag$变换后可以得到$x$的$f$值。
因为单位元是固定的,因此通过$tag$可以直接得到$f$值。

因此我们只需要维护线段树每个结点的$tag$即可。
因为$tag$有可合并性,故线段树可以直接合并,注意合并顺序为从右往左合并(从深往浅合并)。

预处理重链的$tag$

将重链按照链顶深度排序,从最深的重链开始合并。

每次建出当前重链的线段树,将其$f$合并到链顶父亲的$restf$中($restf$代表轻链的$f$和)。
这样,其父亲建立线段树时又会通过$restf$预处理$tag$。
如此重复,最终即可预处理完所有重链的$tag$。

处理修改

修改与预处理类似。
找到需要修改的点,更新链顶$t$的$restf$,消除原有$restf$对$father[t]$的影响,添加新的$restf$的影响,如此不断重复迭代到最顶层。

取出$f(x)$的值

找到对应重链,提取出线段树上$[x,r]$的$tag$,通过单位元复合$tag$计算$f(x)$。

细节

  1. 在修改与预处理的时候,需要先消除原有的影响,再加上新的影响。
    在某些情况下,原有的影响需要事先爬一遍树记录下来,不能爬的时候一边修改一边查询。
  2. 在叶子结点的时候没有选择子树的权利,可能需要特判一下。
  3. 合并$tag$的时候需要从深往浅合并。
  4. 若$tag$是一个向量,将整个向量一起放在线段树中处理会比在外部枚举向量元素,在线段树中一个一个处理快很多。

例题

参考资料

本篇文章有用吗?有用还不快点击!
0%