Mas's Blog
Masellum 的生活日志
树上差分学习笔记

树上差分在 2015 年及 2016 年的 NOIP 中均出现过,在做一类如统计树上节点(或边)的被经过次数等问题时十分常用。

树上差分非常类似于在线性结构上的差分,只是放到了树上。我们考虑在序列上进行差分的操作:对区间 [l,r][l, r] 加一个数 xx 时,我们使 [l]+x[l] + x 而使 [r+1]x[r + 1] - x,在所有修改信息都被处理后,从头到尾统计一遍前缀和就是正确修改后的数组。

树上差分即是将这种操作放在树上。一般我们要考虑的是对于一条树上的简单路径(或者叫做链)的信息进行修改。在这里以统计覆盖次数为例。树上差分有两种类型:一类是对点的信息进行维护,一类是对边的信息进行维护。先来研究维护边的信息的方法。

按照传统的图的存储方式(邻接矩阵或邻接表),直接维护边的信息不易维护,我们用维护点的信息来替代,令点 xx 上保存的信息实际代表 xxxx 的父亲这条边的信息。对于一条链的信息进行修改,应该使被修改的信息不传到这条链之外。显然这里我们不应该自上而下地维护信息,而应该自下而上地维护信息。因此我们应该在链的两个端点处加,而在链的两个端点的 LCA 处减。思考得出结论:设数组 diff[] 为差分数组,u,vu, v 为链的两个端点,lcalca​ 为两个端点的 LCA,则应使 diff[u]++diff[v]++diff[lca] -= 2

维护点的信息的方式与维护边类似,只是 lcalca 这个点这时候也被经过了一次,因此 diff[lca] 应该只自减 11。同时为了只让信息存在于链的范围内,应该令 diff[father[lca]]--

在修改所有信息之后,自下而上 DFS,令一个节点的 diff[] 值加上它的所有儿子的 diff[] 值即为它的被经过次数。

例题:

[USACO15DEC]最大流Max Flow

[JLOI2014]松鼠的新家

Finita la comedia.