差分 记录相邻节点值的差值。这样一来，前缀和就相当于原值了。 树上差分 树上差分基本上就是差分在树上的实现。因为差分的原理，我们先将所有点的权值改变成差分值，再更改一段区间内的所有值时，只需要更改首尾两端的值，如果要求值的话 dfs 重新加上前缀和就是正常的值了。 P3128 [USACO15DEC] Max Flow P 模板题，发现更改任意两点间的值只需要在两点差分值加...

P3384 【模板】重链剖分/树链剖分 适用问题 对一个给定的树，维护（修改、查询）其节点点权/边权，操作可 \(O(\log n)\) 次处理（如路径、子树）。 实现 将一棵树剖分成若干条链，每一条链通过区间数据结构维护。 将一个点的子树中最大的那个做为重儿子，其他的叫做轻儿子，对于所有点的重儿子连的链称为重链。我们将重链作为主链，将轻儿子构成的其他轻链加在重链的后面。很明显，...