树上差分

FJ_00460 · 2024-12-22 19:12:48 · 算法·理论

鼠上差分

前言

树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。

树上差分通常会结合 树基础 和 最近公共祖先 来进行考察。树上差分又分为 点差分 与 边差分，在实现上会稍有不同。

差分数组

思想

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

定义

原数组a:5, 8, 4, 3, 15 差分数组b:5, 3, -4, -1, 12

性质： \sum_{j=1}^{i}b_j

边的差分

• 树上差分一般应用于在树上的路径统计
• 对于一棵树，可以设置差分数组 cnt_i 表述经过边 i （链接 i 到 i 的父亲）的次数。

类比于差分数组，如果要从 u 到 v 都加上一个数，那么就会有 cnt_u++ ,cnt_v ++, cnt[lca] -= 2

性质

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

点的差分

修改点权，那么这条路所包括的LCA点也要被记录下来。

那就导致拆2条链，需要有一条链包括LCA点，再次类比差分数组，那条包括LCA的链就有 cnt_u++, cnt[fa_lca]-- 不包括的就是 cnt_v++, cnt[lca] -- 。

【i ~ j】 + val

dp[i] += bal;

d[j + 1] -= val;