浅说树上差分——点差分

我们前面也学过差分，现在的话我们就把他放到树上来做。因为这是树，所以会有点和边之分，所以树上差分也会分为 点差分 和 边差分 。

引入

树上差分其实和线性差分没有什么区别，只不过是放到了树上的两点，而他们之间的最简路径就是可以类比成线性的两点之间的线段。

所以我们如果要对一条曲线进行操作的话，就是在树上跑差分，那么树上差分数组究竟是什么呢，他又代表着什么意思呢？这是一个值得深思的问题，也是困扰我很久的问题。

树上差分数组本质上存储的是 操纵方式，而不是简单的差值。例如一个点 $x$ 的差分数组 $p[x]=-3$ 代表这个点或这个点所对应的边被减去了3，而不是这个点或这个边等于-3，这是一个易错也易混的点。

相同的，对线性差分数组进行求前缀和的话，我们就可以得到真实的答案的值，那么类似的，在 树上差分数组中求子树和，就可以的到这个点的操纵方式，不过为什么要求子树和，而不求其它的，我也不知道，我也不敢问。

点差分

如果我们现在要对树上的一条路径上的点进行统一操作，比如说 +1 或 -2，我们应该如何完成？
首先是不是很容易想到暴力 dfs ？但是这样的时间复杂度是 $\mathcal{O}(n^2)$ 的，不优秀。但是我们在学什么，是不是在学差分，那为什么不从差分的视角来考虑考虑？

如果我们要对一条 $A\to B$ 的路径进行+1的修改操作，那么首先我们肯定要在点 $A$ 和 $B$ 两个位置进行修改对吧，又因为我们最后是通过求子树和来求得每个点的修改方式，所以不能影响 点 $A$ 和 点 $B$ 所对应的子树，所以我们可以非常明了的得到
$$p[A]++,p[B]++$$
然后我们的目光不断向上看，发现基本上都没有问题，但是在他们的最近公共祖先那里除了岔子，为什么呢？因为二者是从两端慢慢爬上来的，这就会导致他们的 LCA 会被增加两次，所以我们又可以得到
$$p[lca(A,B)]--$$
我们继续往上看，发现点 $A$ 和点 $B$ 的最近公共祖先的父亲在计算子树和的时候任然会被增加一次，但是他应该是不能被修改的，所以我们还可以得到
$$p[fa(lca(A,B))]--$$
继续往上看，发现没有问题了，说明我们的操作就成功的完成了！（看不懂的，看下面的图示）

我们把上述的公式总结一下就是 两个点自己加，他们的lca和lca的爸爸都要减，把它写成代码就是

//dp 为倍增数组，lca为求最近公共祖先的函数
int root=lca(a,b);
p[a]++,p[b]++;
p[root]--,p[dp[root][0]]--;

那么当我们要求所有的答案的时候，也就是要求子树和的时候，我们就可以使用一个时间复杂度为 $\mathcal{O}(n)$ 的 dfs 函数来求解：

//mp为邻接表存储
void get(int x, int fa) {int len = mp[x].size();for (int i = 0; i < len; i++) {if (mp[x][i] == fa) continue;int t = mp[x][i];get(t, x);p[x] += p[t];//差分数组求子树和}
}

看完后是不是感觉非常简单，就只是在树上倍增的基础上对一个数组进行了一点点操作，那么好，我们上实战！

例题1——wwx的出玩

wwx给她的衣柜的有 n 个隔间，隔间编号为1到 n 。她有 k 天要和她的男朋友出去玩，第 i 次玩耍wwx会穿隔间 si 到隔间 ti 的衣服，每次穿这些衣服，都会给它们带来一个单位的损坏，你作为她的男朋友，请计算损坏程度最大的衣服的损坏程度是多少。

分析与解答

不难发现，这道题就是一道裸的点差分问题，所以我们直接套模板，顺便也把模板给你了。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e5;
vector<int> mp[INF];
int ans,dp[INF][20],deep[INF],num[INF];//num为差分数组void prepare(int x,int fa){for (int j=1;(1<<j)<=deep[x]-1;j++){dp[x][j]=dp[dp[x][j-1]][j-1];} int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];deep[t]=deep[x]+1,dp[t][0]=x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]<deep[y])swap(x,y);int index=__lg(deep[x]-deep[y]);for (int i=index;i>=0;i--){if (deep[dp[x][i]]>=deep[y])x=dp[x][i];if (deep[x]==deep[y])break;}if (x==y)return x;for (int i=18;i>=0;i--){if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0];
}void get(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get(t,x);num[x]+=num[t];}ans=max(ans,num[x]);//求得最大值
}
int main(){int n,k;cin>>n>>k;for (int i=1;i<n;i++){int u,v;cin>>u>>v;mp[u].push_back(v);mp[v].push_back(u);} deep[1]=1;prepare(1,-1);for (int i=1;i<=k;i++){int s,t;cin>>s>>t;int root=lca(s,t);num[s]++,num[t]++,num[root]--,num[dp[root][0]]--;}get(1,-1);cout<<ans;return 0;
}

例题2——松鼠的新家

题目传送门

分析与解答

这道题其实也是裸题，我们稍微分析一下就知道它的那个参观路线是可以被分成多个区间修改的，但是这样的话，他们的端点的位置，会被重复计算，所以要特判

#include<bits/stdc++.h>
using namespace std;
const int INF=3e5+10;
vector<int> mp[INF];
int ans,dp[INF][20],deep[INF];
int a[INF],num[INF];void prepare(int x,int fa){for (int j=1;(1<<j)<=deep[x]-1;j++){dp[x][j]=dp[dp[x][j-1]][j-1];} int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];deep[t]=deep[x]+1,dp[t][0]=x;prepare(t,x); }
}int lca(int x,int y){if (deep[x]<deep[y])swap(x,y);int index=__lg(deep[x]-deep[y]);for (int i=index;i>=0;i--){if (deep[dp[x][i]]>=deep[y])x=dp[x][i];if (deep[x]==deep[y])break;}if (x==y)return x;for (int i=18;i>=0;i--){if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0];
}void get(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get(t,x);num[x]+=num[t];}ans=max(ans,num[x]);
}
int main(){int n;cin>>n;for (int i=1;i<=n;i++){scanf("%d",&a[i]);}for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);mp[u].push_back(v);mp[v].push_back(u);} deep[1]=1;prepare(1,-1);for (int i=1;i<n;i++){int s=a[i],t=a[i+1];int root=lca(s,t);num[s]++,num[t]++,num[root]--,num[dp[root][0]]--;}get(1,-1);for (int i=2;i<=n;i++){num[a[i]]--;}for (int i=1;i<=n;i++){printf("%d\n",num[i]);}return 0;
}