专栏文章

树上差分

FFJ_00460
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqp5qfv
此快照首次捕获于
2025/12/04 08:27
3 个月前
此快照最后确认于
2025/12/04 08:27
3 个月前
查看原文

鼠上差分

前言

树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。
树上差分通常会结合 树基础 和 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分，在实现上会稍有不同。

差分数组

思想

  • 类似于数学中的求导和积分，差分可以看成前缀和的逆运算。

定义

原数组a:5, 8, 4, 3, 15 差分数组b:5, 3, -4, -1, 12
性质：∑j=1ibj\sum_{j=1}^{i}b_j

边的差分

  • 树上差分一般应用于在树上的路径统计
  • 对于一棵树，可以设置差分数组 cnticnt_i 表述经过边 i （链接 i 到 i 的父亲）的次数。
类比于差分数组，如果要从 u 到 v 都加上一个数，那么就会有 cntu++,cntv++,cnt[lca]−=2cnt_u++ ,cnt_v ++, cnt[lca] -= 2

性质

  • 任意两点之间有且只有一条简单路径
  • 如果是一颗无根树，那么确定根节点后，除根节点外的每个点外每个点有且只有一个父亲节点。

点的差分

修改点权，那么这条路所包括的LCA点也要被记录下来。
那就导致拆2条链，需要有一条链包括LCA点，再次类比差分数组，那条包括LCA的链就有 cntu++,cnt[falca]−−cnt_u++, cnt[fa_lca]-- 不包括的就是 cntv++,cnt[lca]−−cnt_v++, cnt[lca] --。
【i ~ j】 + val
dp[i] += bal;
d[j + 1] -= val;

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...