树上差分

本人被树上差分困扰了很久！！今天正式来攻克一下。

快速回顾：差分和前缀和

考虑这样一个问题：给一个数列 $\{a_i\}^n_1$，初始时都是 $0$，要求支持以下两种操作：

• 给定 $[L,R],k$：让 $a_L\to a_R$ 增加 $k$。
• 给定 $x$：输出 $a_x$。

先不要想什么线段树，有什么可以不暴力修改每个节点的方法吗？当然有！我们可以维护一个差分数组。修改 $[L,R]$ 时，

• 让 $b_L\leftarrow b_L+k$。
• 让 $b_{R+1}\leftarrow b_{R+1}-k$。

要查询 $a_x$ 时，我们就计算 $b_1\to b_x$ 的前缀和就好了。

什么是树上差分

树上差分解决这样的问题：

• 给定树上两个节点 $u,v$ 和数 $k$：让 $u\to v$ 这条路径上的计数器 $+k$。

和数列上的差分有些不同，这里应用的是 “子树和” 思想。同时又分为点差分和边差分两种。

点差分

图摘自 oi-wiki

如图，我们想要让路径 $S\to T$ 上的节点计数器 $+k$，这样做：

• $\text{cnt}_S\leftarrow\text{cnt}_S+k$，$\text{cnt}_T\leftarrow\text{cnt}_T+k$。（把两端点的差分计数器 $+k$）
• $\text{cnt}_{LCA}\leftarrow\text{cnt}_{LCA}-k$。（把 LCA 的差分计数器 $-k$）
• $\text{cnt}_{f(LCA)}\leftarrow\text{cnt}_{f(LCA)}-k$。（把 LCA 的父节点的差分计数器 $-k$）

你可能会疑惑，那我们怎么获取，比如 $\text{cnt}_{LCA}$ 的值呢？我们只要计算以 $LCA$ 为顶点的子树的差分计数器之和就行了！！神奇！