两种常见的树上差分
树上差分忘完了……康复一下。
记 $x$ 节点的父亲为 $fa(x)$ 。
记 $x,y$ 节点的LCA为 $lca$ 。
记权值数组为 $w_x$ ，差分数组为 $D_x$ 。
记DFS序中 $IN_x$ 表示 $x$ 的入栈序，$OUT_x$ 表示 $x$ 的出栈序。
路径修改，单点查询
我们先考虑将 $x$ 到根节点路径上的点都加上 $k$ 的权值：我们给 $D_x$ 加上 $k$ ，然后每次查询 $w_x$ 的时候通过求 $x$ 子树中 $D$ 的和的方式来得到 $w_x$ 。
那么任意一条路径实际上只要拆成上面的形式即可（容斥）：如果要将 $x\to y$ 路径上的点都加上 $k$ 的权值，我们可以给 $D_x$ 加上 $k$ ，$D_y$ 加上 $k$ ，$D_{lca}$ 减去 $k$ ，$D_{fa(lca)}$ 减去 $k$ ，这样就完成了路径修改。
可以使用树状数组快速修改和查询。
单点修改，路径查询
定义 $S_x$ 表示 $x$ 到根节点路径上的权值和，那么每次给 $w_x$ 加上 $k$ 时候，我们将 $x$ 子树中的全部 $S$ 都加上 $k$ ，就可以维护 $S$ 数组了。
但是这样复杂度开销太大了，我们使用差分。将 $S$ 定义到DFS序上：$S_i$ 表示 $IN_x=i$ 的节点 $x$ 到根节点路径上的权值和，定义 $D_i=S_i-S_{i-1}$ ，那么每次 $[IN_x,OUT_x]$ 中 $S$ 加上 $k$ 时，只有 $D_{IN_x}$ 增加了 $k$ ，$D_{OUT_x+1}$ 减少了 $k$ ，其他 $D$ 都没有变化。
然后每次求 $S_i$ 时只需要询问 $\sum_{j=1}^{i}D_j$ 即可，也可以用树状数组快速修改和查询。
路径查询时也使用上述容斥即可。
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！
请不要发毫无意义或内容不文明的评论。与本文无关评论请发留言板！
