差分
差分的基本模型是:
若有一数组 \(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,其余和模型同理。
边差分