Sweetlemon 的博客

Sweetlemon 的博客

树上前缀和与树上差分

posted on 2019-06-26 16:22:42 | under 算法笔记 |

树上前缀和与树上差分都是树链剖分优秀的离线替代品,配合树状数组还可以进一步处理在线的情况。

树上前缀和

树上前缀和——某个节点到根的路径上的每个点的权值和

求法: $\mathrm{dfs}$ 时带参数传递下去即可

用法: $x\rightarrow y$ 的权值和

  1. 点权: $s[x]+s[y]-s[\mathrm{lca}]-s[\mathrm{par}(\mathrm{lca})]$

  2. 边权: $s[x]+s[y]-2s[\mathrm{lca}]$

树上差分

树上差分——某个节点对它到根的路径上的每个点的贡献

求法:修改 $x\rightarrow y$ 上每个点/边的权值时:

  1. 点权: $d[x]+=w,\ d[y]+=w,\ d[\mathrm{lca}]-=w,\ d[\mathrm{par}(\mathrm{lca})]-=w$

  2. 边权: $d[x]+=w,\ d[y]+=w,\ d[\mathrm{lca}]-=2w$

用法:某个节点的权值即为它子树所有节点的差分和

点权和边权

我们的树上前缀和与树上差分(还有树链剖分,小声)都是基于点权的。那么如果遇到边权的问题,如何解决呢?

当然是把边权分配到点上了啊。由于每个点的父节点是唯一的,因此每个点到父节点的连边是唯一的。那么,我们把边权分配到子节点上,也就是分配到深度较大的端点上,问题就解决了。