浅谈DFS序的应用

发布于 26 天前  46 次阅读


转载自

对某个节点x权值加上一个数W, 查询某个子树x里所有点权的和.

由于x的子树在DFS序中是连续的一段, 只需要维护一个dfs序列,用树状数组实现:单点修改区间查询.

对节点xy的最短路上所有点权都加一个数W,查询某个点的权值.

这个操作等价于

a. 对x到根节点路径上所有点权加W
b. 对y到根节点路径上所有点权加W
c. 对LCA(x, y)到根节点路径上所有点权值减W
d. 对LCA(x,y)的父节点 fa(LCA(x, y))到根节点路径上所有权值减W

于是要进行四次这样从一个点到根节点的区间修改.将问题进一步简化, 进行一个点X到根节点的区间修改, 查询其他一点Y时,只有XY的子树内, XY的值才有贡献且贡献值为W.当单点更新X时,X实现了对X到根的路径上所有点贡献了W.于是只需要更新四个点(单点更新) ,查询一个点的子树内所有点权的和(区间求和)即可.

对节点XY的最短路上所有点权都加一个数W, 查询某个点子树的权值之和.

同问题2中的修改方法, 转化为修改某点到根节点的权值加/减W
当修改某个节点A, 查询另一节点B时
只有AB的子树内, Y的值会增加
W * (dep[A] - dep[B] + 1) => W * (dep [A] + 1) - W * dep[B]
那么我们处理两个数组就可以实现:
处理出数组Sum1,每次更新W*(dep[A]+1), 数组Sum2,每次更新W.
每次查询结果为Sum1(R[B]) – Sum1(L[B]-1) - (Sum2(R[B]) – Sum2(L[B]-1)) * dep [B].

对某个点X权值加上一个数W, 查询XY路径上所有点权之和.

XY路径上所有的点权之和, 和前面XY路径上所有点权加一个数相似
这个问题转化为: X到根节点的和 +Y到根节点的和 - LCA(x, y)到根节点的和 - fa(LCA(x,y)) 到根节点的和
更新某个点x的权值时,只会对它的子树产生影响,对x的子树的每个点到根的距离都加了W
那么我们用”刷漆”(差分前缀和),更新一个子树的权值.给L[x]加上W,给R[x]+1减去W,那么sum(1~L[k])就是k到根的路径点权和.

对节点X的子树所有节点加上一个值W, 查询X到Y的路径上所有点的权值和

同问题4把路径上求和转化为四个点到根节点的和
X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - parent(LCA(x,y)) 到根节点的
再用刷漆只更新子树.
修改一点A, 查询某点B到根节点时, 只有BA的子树内, AB才有贡献.
贡献为W * (dep[B] - dep[A] + 1) => W * (1 - dep[A]) + W * dep[B]
和第三题一样, 用两个sum1,sum2 维护 $W (dep[A] + 1),和W.
最后答案就是
sum2
dep[B]-sum1$.

对子树X里所有节点加上一个值W, 查询某个点的值.

对DFS序来说, 子树内所有节点加W, 就是一段区间加W.
所以这个问题就是 区间修改, 单点查询.树状数组+刷漆.

对子树X里所有节点加上一个值W, 查询某个子树的权值和.

子树所有节点加W, 就是某段区间加W, 查询某个子树的权值和, 就是查询某段区间的和区间修改区间求和,用线段树可以很好解决.


朴实沉毅