• 欢迎光临~

树上差分

开发技术 开发技术 2022-07-26 次浏览

一个与本文关系不大的小背景

一个朋友问我好几次了树上差分的题树链剖分能不能做,后来学长讲明白了,能做,只不过一个复杂度看点,一个复杂度看链,一些题目可以卡掉树剖但卡不掉树上差分。

前言

想了解树上差分,要先了解差分
不了解差分的看这前缀和与差分
这里我们是把差分放到树上

进入正题

对于树上差分,重要的是它的思想,毕竟题目或许都能用树剖过我找不到除了卡时间外树剖做不了但差分能做的例子
有一棵n个点的树,节点都为0,现在有一些操作,让a到b两点之间的所有点权值+1
这里,一个点+1的含义不是这个点的点权+1,而是这个点到根节点的路径上的点的权值都+1,如果一个点被访问,那么他的父亲也会被访问

分类

树上差分分两种,边差分和点差分
点差分很简单,在a,b两点上+1,但是,我们只是让a到b路径上的点权值+1,不牵扯上面的点,所以,我们要在2个点上-1来减去多余的,我们要在LCA上-1,但是LCA也属于这条路径上的点,所以另一个-1就放在LCA的父亲上
总结一下,就是a+1,b+1,lca-1,fa[lca]-1
边差分需要提前预处理一下,将边权下落到这条边下面的点上,边差分的lca与点差分的lca不同,lca上存的边不属于这条路径,所以lca上可以-2
总结一下,就是a+1,b+1,lca-2

结束

代码?自己根据题目来,答题套路就是上面那种
好短呀

程序员灯塔
转载请注明原文链接:树上差分
喜欢 (0)