树上差分

树上差分主要是对树上的路径进行修改和查询操作,只对一些重要节点进行修改,最后通过(dfs)计算差分数组的前缀和得到最终节点的值,从而降低时间复杂度,实现差分优化
点差分
如果对(u,v)之间路径上的节点的点权增加(x),则需要对差分数组进行的操作为:

[diff[u]+=x ]

[diff[v]+=x ]

[diff[lca(u,v)]-=x ]

[diff[fa[lca(u,v)]]-=x (lca(u,v) eq root) ]

边差分
设每条边的边权通过子节点存储
如果对(u,v)之间路径上的边的边权增加(x),则需要对差分数组进行的操作为:

[diff[u]+=x ]

[diff[v]+=x ]

[diff[lca(u,v)]-=2*x (lca(u,v) eq root) ]

原文地址:https://www.cnblogs.com/fxq1304/p/13640036.html