@Junlier
2018-11-06T22:14:42.000000Z
字数 881
阅读 2380
数学方法——差分
啦啦啦~树上差分一点都不难(难的是天天爱跑步)
首先得知道差分这个东西吧! 简单差分
在讲树上差分之前,首先需要知道树的以下两个性质:
- 任意两个节点之间有且只有一条路径。
- 一个节点只有一个父亲节点(即只有一条返祖边)
可以发现所有树上两点 ,的路径可拆为:--->--->
最近考树上差分考得还挺多的
所以想要阿克的巨佬们最好学一下
像差分一样,树上差分也有前缀和思想
一个点的真实权值是一个点子树内所有差分后的权值之和(额,有点拗口没关系)
总的来说就是一个点的差分数组最后的值是整个子树内差分数组的和,再加进点的权值里
所以怎么差分呢
先抛出一个问题:给你个操作,问你每次在路径上给所有点的权值,问你最后点的权值情况(时间复杂度:请你尽量跑得快)
我们考虑差分,时刻记住上面的那句加粗的话
首先在p上面对差分数组+1,再在q上面对差分数组+1,在Lca(p,q)处对差分数组-1,在fa[Lca(p,q)]处对差分数组-1
我们根据上面所说的方法统计一遍子树差分数组和,就会发现正如所想
那么我们就可以推广到所有的情况了是吧
显然这样差分的修改复杂度是的(求),只要最后再一边扫就是吧
你甚至可以用求来优化掉每次修改的时候查的那个
如果需要代码板子的话可以看下面例题。。。