一、差分
给定一个序列(a_1,…,a_n)，定义一个序列(b_i=a_i-a_{i-1})，即为差分数组。
听这个名字就知道，差分数组就是记录紧挨着两个数的差值。
该数组有以下性质：
- 差分数组中([l,r])的和即为(a_r-a_{l-1})；
- 差分数组并不是固定的。不同方式的差分数组有不同的功能。
大概就这么多，视情况而定。
二、树上差分
例题：闇の連鎖
网址：https://www.acwing.com/problem/content/354/
传说中的暗之连锁被人们称为 Dark。
Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。
经过研究，你发现 Dark 呈现无向图的结构，图中有 (N) 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。
Dark 有 (N–1) 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。
另外，Dark 还有 (M) 条附加边。
你的任务是把 Dark 斩为不连通的两部分。
一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。
一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。
但是你的能力只能再切断 Dark 的一条附加边。
现在你想要知道，一共有多少种方案可以击败 Dark。
注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。
输入格式
第一行包含两个整数 (N) 和 (M)。
之后 (N–1) 行，每行包括两个整数 (A) 和 (B)，表示 (A) 和 (B) 之间有一条主要边。
之后 (M) 行以同样的格式给出附加边。
输出格式
输出一个整数表示答案。
数据范围
(N≤100000,M≤200000),数据保证答案不超过(2^31−1)
输入样例：
4 1
1 2
2 3
1 4
3 4
输出样例：
3
经典树上差分模板，每次加边的时候相当于将两端点差分数组+1，由于该差分数组记录的是该点的上面那条边，所以要注意边界条件（根节点）。另外，在最近公共祖先-2。
C++ AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
const int SIZE = 100000 + 5;
queue <int> Q;
vector <int> G[SIZE];
int n, t, m, cnt = 0, sum[SIZE], dep[SIZE], F[SIZE][40];
void init()
{
t = log(n) / log(2);
for(int i = 0; i <= n; ++ i) G[i].clear();
memset(sum, 0, sizeof(sum));
memset(F, -1, sizeof(F));
return;
}
int LCA(int x, int y)
{
if(dep[x] > dep[y]) swap(x, y);
for(int i = t; i >= 0; -- i) if(dep[F[y][i]] >= dep[x]) y = F[y][i];
if(x == y) return x;
for(int i = t; i >= 0; -- i)
{
if(F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
}
return F[y][0];
}
void BFS()
{
while(!Q.empty()) Q.pop();
memset(dep, 0, sizeof(dep));
dep[1] = 1;
F[1][0] = 0;
Q.push(1);
int u, v;
while(Q.size())
{
u = Q.front();
Q.pop();
for(int i = 0; i < G[u].size(); ++ i)
{
v = G[u][i];
if(dep[v]) continue;
dep[v] = dep[u] + 1;
Q.push(v);
F[v][0] = u;
for(int k = 1; k <= t; ++ k) F[v][k] = F[F[v][k - 1]][k - 1];
}
}
return;
}
void solve(int u)
{
int v;
for(int i = 0; i < G[u].size(); ++ i)
{
v = G[u][i];
if(v != F[u][0]) solve(v);
}
for(int i = 0; i < G[u].size(); ++ i)
{
v = G[u][i];
if(v != F[u][0]) sum[u] += sum[v];
}
for(int i = 0; i < G[u].size(); ++ i)
{
v = G[u][i];
if(v == F[u][0]) continue;
if(sum[v] == 0) cnt += m;
else if(sum[v] == 1) ++ cnt;
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
init();
for(int i = 1; i < n; ++ i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
BFS();
for(int i = 0; i < m; ++ i)
{
int u, v;
scanf("%d %d", &u, &v);
++ sum[u];
++ sum[v];
sum[LCA(u, v)] -= 2;
}
solve(1);
printf("%d
", cnt);
return 0;
}
练习：松鼠的新家
网址：https://www.luogu.com.cn/problem/P3258
题目描述
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有 (n) 个房间，并且有 (n-1) 根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。
松鼠想邀请小熊前来参观，并且还指定一份参观指南，他希望小熊能够按照他的指南顺序，先去 (a_1)，再去 (a_2)，最后到 (a_n)，去参观新家。可是这样会导致重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
小熊是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间 (a_n) 是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入格式
第一行一个正整数 (n)，表示房间个数第二行 (n) 个正整数，依次描述 (a_1, a_2,cdots,a_n)。
接下来 (n−1) 行，每行两个正整数 (x,y)，表示标号 (x) 和 (y) 的两个房间之间有树枝相连。
输出格式
一共 (n) 行，第 (i) 行输出标号为 (i) 的房间至少需要放多少个糖果，才能让小熊有糖果吃。
输入输出样例
输入 #1
5
1 4 5 3 2
1 2
2 4
2 3
4 5
输出 #1
1
2
1
2
1
说明/提示
对于全部的数据，2 le n le 3 imes 10^5，1 le a_i le n。
这道题按照上一题思路，关注行进点只停留一次，最后一步该房间不用放糖。
C++ AC代码
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int SIZE = 300000 + 5;
vector <int> G[SIZE];
queue <int> Q;
int n, t, a[SIZE], b[SIZE], ans[SIZE], dep[SIZE], F[SIZE][40];
void BFS()
{
while(Q.size()) Q.pop();
memset(dep, 0, sizeof(dep));
dep[1] = 1;
F[1][0] = 0;
Q.push(1);
while(Q.size())
{
int u = Q.front();
Q.pop();
for(int i = 0; i < G[u].size(); ++ i)
{
int v = G[u][i];
if(dep[v]) continue;
dep[v] = dep[u] + 1;
Q.push(v);
F[v][0] = u;
for(int j = 1; j <= t; ++ j) F[v][j] = F[F[v][j - 1]][j - 1];
}
}
return;
}
int LCA(int x, int y)
{
if(dep[x] > dep[y]) swap(x, y);
for(int i = t; i >= 0; -- i) if(dep[F[y][i]] >= dep[x]) y = F[y][i];
if(x == y) return y;
for(int i = t; i >= 0; -- i)
{
if(F[x][i] != F[y][i])
x = F[x][i], y = F[y][i];
}
return F[y][0];
}
void dfs(int u, int Fa)
{
ans[u] = b[u];
for(int i = 0; i < G[u].size(); ++ i)
{
int v = G[u][i];
if(v != Fa)
{
dfs(v, u);
ans[u] += ans[v];
}
}
return;
}
int main()
{
memset(b, 0, sizeof(b));
scanf("%d", &n);
t = log(n) / log(2);
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i) G[i].clear();
int x, y, lca, Fa;
for(int i = 1; i < n; ++ i)
{
scanf("%d %d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
BFS();
x = a[1], y = a[2], lca = LCA(x, y), Fa = F[lca][0];
++ b[x], ++ b[y], -- b[lca], -- b[Fa];
for(int i = 2; i < n; ++ i)
{
x = y, y = a[i + 1];
lca = LCA(x, y), Fa = F[lca][0];
if(lca == x)
{
-- b[x];
++ b[y];
}
else
{
lca = LCA(F[x][0], y), Fa = F[lca][0];
++ b[F[x][0]], ++ b[y];
-- b[lca], -- b[Fa];
}
}
dfs(1, 0);
for(int i = 1; i <= n; ++ i)
{
if(i == a[n]) -- ans[i];
printf("%d
", ans[i]);
}
return 0;
}
例题：雨天的尾巴
网址：https://www.acwing.com/problem/content/355/
有 (n) 个点，形成一个树状结构。
有 (m) 次发放操作，每次选择两个点 (x,y)，对 (x) 到 (y) 的路径上（包括 (x,y)）的每个点发放一袋 (z) 类型的物品。
求完成所有发放操作后，每个点存放最多的是哪种类型的物品。
输入格式
第一行两个正整数(n,m)，含义如题目所示。
接下来(n-1)行，每行两个数((a,b))，表示((a,b))间有一条边。
再接下来(m)行，每行三个数((x,y,z))，含义如题目所示。
输出格式
共(n)行，第(i)行一个整数，表示第(i)座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。
如果某座房屋里没有救济粮，则对应一行输出(0)。
数据范围
(1≤n,m≤100000,1≤z≤10^9)
输入样例：
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
输出样例：
2
3
3
0
2
累和用线段树合并即可（非常快）。
C++ AC代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#define pii pair <int, int>
using namespace std;
const int SIZE = 100000 + 5;
struct SegmentTree
{
int lc, rc;
int dat, pos;
} tree[SIZE << 6];
vector <int> G[SIZE];
int in[SIZE][3], ans[SIZE];
int n, m, t, tot = 0, num = 0, root[SIZE], dep[SIZE], F[SIZE][40], book[SIZE];
int build()
{
++ tot;
tree[tot].lc = tree[tot].rc = tree[tot].dat = 0;
return tot;
}
void discrete()
{
sort(book + 1, book + m + 1);
num = unique(book + 1, book + m + 1) - (book + 1);
return;
}
int query(int x)
{
int L = 1, R = num, mid;
while(L < R)
{
mid = L + ((R - L) >> 1);
if(book[mid] < x) L = mid + 1;
else R = mid;
}
return R;
}
void BFS()
{
queue <int> Q;
while(!Q.empty()) Q.pop();
memset(dep, 0, sizeof(dep));
F[1][0] = 0;
Q.push(1);
dep[1] = 1;
while(Q.size())
{
int u = Q.front();
Q.pop();
for(int i = 0; i < G[u].size(); ++ i)
{
int v = G[u][i];
if(dep[v]) continue;
dep[v] = dep[u] + 1;
Q.push(v);
F[v][0] = u;
for(int i = 1; i <= t; ++ i) F[v][i] = F[F[v][i - 1]][i - 1];
}
}
return;
}
int LCA(int x, int y)
{
if(dep[x] > dep[y]) swap(x, y);
for(int i = t; i >= 0; -- i) if(dep[F[y][i]] >= dep[x]) y = F[y][i];
if(y == x) return y;
for(int i = t; i >= 0; -- i)
{
if(F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
}
return F[x][0];
}
void insert(int p, int l, int r, int val, int d)
{
if(val > r || val < l) return;
if(l == r)
{
tree[p].dat += d;
tree[p].pos = l;
return;
}
int mid = (l + r) >> 1;
if(val <= mid)
{
if(!tree[p].lc) tree[p].lc = build();
insert(tree[p].lc, l, mid, val, d);
}
else
{
if(!tree[p].rc) tree[p].rc = build();
insert(tree[p].rc, mid + 1, r, val, d);
}
int lc = tree[p].lc, rc = tree[p].rc;
if(tree[lc].dat < tree[rc].dat)
{
tree[p].pos = tree[rc].pos;
tree[p].dat = tree[rc].dat;
}
else
{
tree[p].pos = tree[lc].pos;
tree[p].dat = tree[lc].dat;
}
return;
}
int merge(int p, int q, int l, int r)
{
if(!p) return q;
if(!q) return p;
if(l == r)
{
tree[p].dat += tree[q].dat;
return p;
}
int mid = l + r >> 1;
tree[p].lc = merge(tree[p].lc, tree[q].lc, l, mid);
tree[p].rc = merge(tree[p].rc, tree[q].rc, mid + 1, r);
int lc = tree[p].lc, rc = tree[p].rc;
if(tree[lc].dat < tree[rc].dat)
{
tree[p].dat = tree[rc].dat;
tree[p].pos = tree[rc].pos;
}
else
{
tree[p].dat = tree[lc].dat;
tree[p].pos = tree[lc].pos;
}
return p;
}
void dfs(int u, int Fa)
{
for(int i = 0; i < G[u].size(); ++ i)
{
int v = G[u][i];
if(v != Fa)
{
dfs(v, u);
root[u] = merge(root[u], root[v], 1, num);
}
}
ans[u] = book[tree[root[u]].pos];
return;
}
int main()
{
scanf("%d %d", &n, &m);
t = log(n) / log(2);
for(int i = 1; i < n; ++ i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
BFS();
for(int i = 1; i <= n; ++ i)
{
root[i] = build();
}
for(int i = 1; i <= m; ++ i)
{
scanf("%d %d %d", &in[i][0], &in[i][1], &in[i][2]);
book[i] = in[i][2];
}
discrete();
for(int i = 1; i <= m; ++ i)
{
int u = in[i][0], v = in[i][1], w = in[i][2];
int val = query(w), lca = LCA(u, v), Fa = F[lca][0];
insert(root[u], 1, num, val, 1);
insert(root[v], 1, num, val, 1);
insert(root[lca], 1, num, val, -1);
if(Fa) insert(root[Fa], 1, num, val, -1);
}
dfs(1, 0);
for(int i = 1; i <= n; ++ i) printf("%d
", ans[i]);
return 0;
}
参考文献
- 《算法竞赛进阶指南》0x63