差分性质
差分可以理解为前缀和的逆运算。这种策略的定义是令
$$b_i=\begin{cases}a_i-a_{i-1} &,i\in[2,n]\\a_1&,i=1 \end{cases}$$
所以，我们可以推导出一下性质：
$a_i$的值就是$b_i$的前缀和，即：
$$\sum^n_{i=1}b_i$$
计算$a_i$的前缀和$sum$，即：
$$sum=\sum^n_{i=1}a_i=\sum^n_{i=1}\sum^i_{j=1}b_j=\sum^n_{i=1}(n-i+1)b_i$$
差分应用
简单差分
差分数组可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。
问题
例题：
第一行有两个整数$n,p$，代表元素个数和操作次数。
第二行有$n$个数，$a_1 \sim a_n$，代表各个元素的初始值。
接下来$p$行，每行有三个数，$x$，$y$，$z$，代表给第$z$个到第$y$个元素加上$z$。
（没错，就是洛谷上的“语文成绩”这道题）
代码
read(n,p);
for(int i=1;i<=n;i++){
read(a[i]);
b[i]=a[i]-a[i-1];
}
while(p--){
read(x,y,z);
b[x]+=z;
b[y+1]-=z;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];
ans=Min(ans,a[i]);
}
print(ans);树上差分
树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。
树上差分问题经常和最近公共祖先（LCA）结合，树上差分分为点差分和变差分，在实现上稍稍存在不同。
点差分
问题
选取树上的两个点$S,T$，找到从$S$到$T$的一条最短路径进行访问，最终询问每个点被访问的次数。
没错，就是洛谷上“松鼠的新家”这一道题。
分析
找出$S,T$之间的这一条路径
归纳可得，从树上的一个点走到另一个点有且仅有一条路径（不重复经过一个点）并且这条路径一定经过了这两个点的最近公共祖先。所以可以先使用倍增或者树链剖分的方法求出最近公共祖先。
void add(int x,int y){
e[++nxt].to=y;
e[nxt].nxt=g[x];
g[x]=nxt;
return;
}
void dfs_fa(int x,int fa){
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int k=g[x];k;k=e[k].nxt){
int y=e[k].to;
if(y==fa)
continue;
dfs_fa(y,x);
}
return;
}
int get_lca(int s,int t){
if(dep[s]<dep[t])
swap(s,t);
for(int i=20;i>=0;i--){
if(f[s][i]!=0&&dep[f[s][i]]>=dep[t])
s=f[s][i];
}
if(s==t)
return s;
for(int i=20;i>=0;i--)
if(f[s][i]!=0&&f[t][i]!=0&&f[s][i]!=f[t][i]){
s=f[s][i];
t=f[t][i];
}
return f[s][0];
}
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}修改访问次数
如果我们采用暴力方法对每个点进行访问，有太多的路径需要访问，一定会爆TLE，我们考虑使用差分解决问题。又因为树是递归定义的，我们采用从叶子到根的顺序建立差分数组，以下图举例：
那么，根据差分的原理，我们对下图进行如下修改：
$\begin{aligned}&d_s=d_s+1 \&f(d_{lca})=f(d_{lca})-1 \&d_t=d_t+1\&d_{lca}=d_{lca}-1\end{aligned}$
前两步可以看做是对红色框内点进行差分修改，后两部看做是对蓝色框内的点进行差分修改。
经过多次修改之后，从根节点开始DFS这一棵树，回溯时求差分数组的前缀和即可。
void dfs_ans(int x,int fa){
for(int k=g[x];k;k=e[k].nxt){
int y=e[k].to;
if(y==fa)
continue;
dfs_ans(y,x);
}
pre[fa]+=pre[x];
return;
}
for(int i=2;i<=n;i++){
int lca=get_lca(a[i-1],a[i]);
b[a[i-1]]+=1;
b[f[lca][0]]-=1;
b[a[i]]+=1;
b[lca]-=1;
}代码
Fast 命名空间中包括快读、快输、各种宏定义，不会影响代码阅读，您可以在左侧栏文章《代码模板》中查看具体内容。
#include<bits/stdc++.h>
using namespace std;
namespace Fast{...}
using namespace Fast;
struct Node{
int nxt,to;
}e[M<<1];
int g[M],nxt;
int n,a[M],b[M],x,y,pow2[21],f[M][21],dep[M],pre[M];
void add(int x,int y){
e[++nxt].to=y;
e[nxt].nxt=g[x];
g[x]=nxt;
return;
}
void dfs_fa(int x,int fa){
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int k=g[x];k;k=e[k].nxt){
int y=e[k].to;
if(y==fa)
continue;
dfs_fa(y,x);
}
return;
}
int get_lca(int s,int t){
if(dep[s]<dep[t])
swap(s,t);
for(int i=20;i>=0;i--){
if(f[s][i]!=0&&dep[f[s][i]]>=dep[t])
s=f[s][i];
}
if(s==t)
return s;
for(int i=20;i>=0;i--)
if(f[s][i]!=0&&f[t][i]!=0&&f[s][i]!=f[t][i]){
s=f[s][i];
t=f[t][i];
}
return f[s][0];
}
void dfs_ans(int x,int fa){
for(int k=g[x];k;k=e[k].nxt){
int y=e[k].to;
if(y==fa)
continue;
dfs_ans(y,x);
}
pre[fa]+=pre[x];
return;
}
int main(){
read(n);
pow2[0]=1;
for(int i=1;i<=20;i++){
pow2[i]=pow2[i-1]*2;
}
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<n;i++){
read(x,y);
add(x,y);
add(y,x);
}
dfs_fa(1,0);
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
for(int i=2;i<=n;i++){
int lca=get_lca(a[i-1],a[i]);
b[a[i-1]]+=1;
b[f[lca][0]]-=1;
b[a[i]]+=1;
b[lca]-=1;
}
for(int i=1;i<=n;i++){
pre[i]=b[i];
}
dfs_ans(1,0);
for(int i=2;i<=n;i++)
pre[a[i]]--;
for(int i=1;i<=n;i++){
print(pre[i]);
enter;
}
return 0;
}
