[蓝桥杯学习]?树上差分
2024-01-08 11:32:34
差分
前缀和 sum_i = sum_i-1? + a_i
差分? ? diff_i = a_i - a_i-1
差分的好处
点的差分
问题引入
解决问题
要用到差分的思想,每次从叶子向上的回溯,让父结点+=子结点的cnt值,但是仅仅这样,还不行
回溯的过程中,LCA被加了两次,要减去一,LCA的父结点原本应该没有数值的,但是因为会加上LCA 的值,所以会多1,要减去。
此上操作,便实现了,只是把s t 两个结点的值赋一,便将s到t路径上的点经过次数赋值为1
代码实现
cnt计算的代码实现,如下
void dfs1(int x){
for(int i=head[x];i;i=edge[i].nex){
int u=edge[i].to;
if(u!=fa[x][0]){
dfs1(u);
cnt[x]+=cnt[u];
}
}
return ;
}
cnt[x]+=cnt[u] ,在dfs1 之后,就是从子结点回到父结点后进行cnt相加。
边的差分
问题引入
将路上每条边都权值加z
解决问题
把边塞给点,边的权值放在点上,使用差分的方法,每次修改都是O(1)的时间复杂度,将最后的结果最坏下是O(n)遍历要求的区间,就可以得到区间权值和。
解释为什么要把 dlt[lca(u,v)]-=2x?
因为根据方法,回溯时父结点会加上子结点的权值,所以LCA会加上左右两边的孩子的权值(即边的权值),根据我们给点权值的定义,意思是,会经过该边两次,但是该边没有经过两次,所以会减去2x?
代码实现
与点上的差分一样的
时间复杂度分析
维护的时间复杂度是O(1),最后dfs一遍统计答案,最坏时间复杂度是O(n)
文章来源:https://blog.csdn.net/weixin_73512213/article/details/135367758
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!