差分
差分的基本模型是：
若有一数组 \(a[~] = \{1,1,4,5,1,4\}\)，定义差分数组 \(d[~],~ d_i = a_i-a_{i-1}~(i\in[1,n])\) .
则 \(d[~] = \{1,0,3,1,-4,3\}\) .
现在要对它进行在线区间修改，假设有一次修改为在 \([2,4]\) 上每一位 +1，那么修改后 \(a[~] = \{1,2,5,6,1,4\}\) .
而差分思想只需要在 \(l=2\) 上 +1，\(r+1=5\) 上 -1，即 \(d[~] = \{1,1,3,1,-5,3\}\) .
这是显然的，\(l\) 比 \(l-1\) 大 1， \(r+1\) 比 \(r\) 小 1， \([1,l-1],[l,r],[r+2,n]\) 差值不变。
最后离线用前缀和还原结果：\(a_i = \sum\limits_{j=1}^{i}d_j~(i\in[1,n])\) .
树上差分
然鹅，这次要重点记录的是 树上差分（学了lca才发现有这玩意），分两种：树上点差分，树上边差分。
先讨论初始值为 0 的情况。
点差分
类似地，假如在一棵树上要对 \(x\to y\) 的唯一路径上的所有点 +1，可以定义一个差分数组 \(d\)，则：
\[d_x + 1,~d_y + 1,~d[lca(x,y)] -1,~st[lca(x,y)][0] - 1 \]在深搜回溯时累加儿子差值还原，可以发现，\(lca(x,y)\) 被访问了两次， 所以要在上面多 -1，其余和模型同理。
边差分
标签：思想,差分,修改,差值,数组,lca,运用,树上 From： https://www.cnblogs.com/hi-zwjoey/p/17800066.html