树上差分主要是对树上的路径进行修改和查询操作,只对一些重要节点进行修改,最后通过(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)
]