数据结构专题：树链剖分

数据结构专题：树链剖分

对于一个给定根节点的树，假如说我们现在要想办法完成下面的4种操作：

1.将树上(X)到(Y)节点的最短路径上的所有节点的权值都加上(Z)。

2.求树上(X)到(Y)节点的最短路径上的所有节点的权值之和。

3.将以(X)为根节点的子树内的所有节点的权值加上(Z)。

4.求以(X)为根节点的子树内的所有节点的权值之和。

不谈暴力的话我们首先可能会想到倍增(LCA)，事实上如果不带修改的话(O(logN))的倍增可以说是非常优秀了。但是对于1、3这种修改的要求我们除了暴力以外就基本没有什么其他的方法，就不够我们的要求了。

因此我们引出剖树为链的说法，也就是树链剖分，这是一种可以将树形转化为线形的十分强大的数据结构。

首先在讲解之前我们要知道里面的一些概念：

  1. 重儿子：对于节点(U)的所有子节点(T)，如果(T_i)的子树大小最大，则称(T_i)为(U)的重儿子。
  2. 轻儿子：如上，其余的子节点都是轻儿子。
  3. 重边：节点(U -> T_i)这条边即为重边（(T_i)为(U)的重儿子）
  4. 轻边：如上，剩下的边都是轻边。
  5. 重链：相邻的所有重边连起来就是重链。对于一个叶子结点若它是轻儿子，则自己既是一条链。

显然对于任何一个叶子结点都没有重儿子或者轻儿子。下面有一张图或许便于我们理解。

1560346268187

图中的所有被红框框起来的点就是一条重链。

那么我们对于上面的需求一个一个解答。

操作1：对于两个点(X),(Y)，我们将所属链的链头的深度比较大的定为(X)，然后如果两个点不在一条链里面，我们就把(X)到(X)所属链的链头的所有点的权值都进行修改，(Y)也是一样。直到(X)和(Y)属于同一条链，我们就把(X)到(Y)的路径上的所有的点的权值都修改就可以了。

而这样剖是为了什么呢？你可以发现我们的树形操作变成了好几个链上的操作。而链上的操作我们就可以很简单的使用线段树或者树状数组来进行维护了。同理下面的操作2也是直接套用上面的方法进行查询。

而对于操作3、4呢？我们在实现会进行两次树的遍历，目的就是为了获取我们需要的信息，比如：

Top：改点所在链的顶端

Size：子树大小（包含自身

Deep：节点深度

Fa：父节点。

Son：重儿子

Id：这个玩意叫做Dfs序，是我们为了使用线段树而将整个树的序号重新排了一下的各节点的新序号。

V：这是新序号的点的权值。

具体我们来看两个Dfs：

int Deep[MAXN], Fa[MAXN], Size[MAXN], Son[MAXN] ;
inline void Dfs1(int Now, int Fas, int Deeps) {
	Deep[Now] = Deeps, Fa[Now] = Fas, Size[Now] = 1 ;
	int Maxson = - 1 ;
	for (int i = H[Now] ; i ; i = E[i].Next) {
		if (E[i].T == Fas) continue ;
		Dfs1(E[i].T, Now, Deeps + 1) ;
		Size[Now] += Size[E[i].T] ;
		if (Size[E[i].T] > Maxson)
			Son[Now] = E[i].T, Maxson = Size[E[i].T] ;
	}
}

int Id[MAXN], Top[MAXN], Cnt ;
inline void Dfs2(int Now, int Tops) {
	Id[Now] = ++ Cnt, V[Cnt] = W[Now], Top[Now] = Tops ;
	if (! Son[Now]) return ;
	Dfs2(Son[Now], Tops) ;
	for (int i = H[Now] ; i ; i = E[i].Next) {
		if (E[i].T == Fa[Now] || E[i].T == Son[Now])
			continue ;
		Dfs2(E[i].T, E[i].T) ;
	}
}

然后对于上面给的样图的Dfs序就是：

1560347005994

这显然是很简单的。那么我们上面讲的操作1、2也就很显而易见了。

inline int Range(int X, int Y) {
	int Ans = 0 ;
	while (Top[X] != Top[Y]) {
		if (Deep[Top[X]] < Deep[Top[Y]] ) swap(X, Y) ;
		int Res = Query(1, Id[Top[X]], Id[X]) ;
		Ans = (Ans + Res) % Mod ; X = Fa[Top[X]] ;
	}
	if (Deep[X] > Deep[Y]) swap(X, Y) ;
	int Res = Query(1, Id[X], Id[Y]) ;
	Ans += Res ; return Ans % Mod ;
}
inline void Change(int X, int Y, int K) {
	K %= Mod ;
	while (Top[X] != Top[Y]) {
		if (Deep[Top[X]] < Deep[Top[Y]]) swap(X, Y) ;
		SegChange(1, Id[Top[X]], Id[X], K) ;
		X = Fa[Top[X]] ;
	}
	if (Deep[X] > Deep[Y]) swap(X, Y) ;
	SegChange(1, Id[X], Id[Y], K) ;
}

然后对于3、4操作，我们是要讲某一个点的所有后代的权值全部修改，而根据Dfs序我们可以知道这个点以及其所有后代的Dfs序一定是连续的(Id[Now]->Id[Now] + Size[Now] - 1)，那么我们也就可以直接用线段树维护。

inline int GetSon(int Now) {
	return Query(1, Id[Now], Id[Now] + Size[Now] - 1) % Mod ;
}
inline void Point(int Now, int K) {
	SegChange(1, Id[Now], Id[Now] + Size[Now] - 1, K % Mod) ;
}

而上面的(Segchange)和(query)都是最基本的线段树操作，我想不用进行特意的说明了。

而总的时间复杂度呢？线段树的所有操作都是(O(logN))的，而我们的剖树操作也都是(O(logN))，于是整个树链剖分的时间复杂度就是(O(log^2N))，可是比(LCA)查询+暴力修改要优得多了吧。

下面给出洛谷的模板题的代码。Link

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define LS (Now << 1)
#define RS ((Now << 1) | 1)
#define Mid ((L + R) >> 1)
#define E_Mid ((G[Now].L + G[Now].R) >> 1)

using namespace std ;
typedef long long LL ;
const int MAXN = 200010, MAXM = 400010 ;
const int Inf = 0x7fffffff ;

int N, M, Root, Mod, H[MAXN], Tot, V[MAXN] ;
struct EDGE {
	int F, T, Next ;
}	E[MAXM << 1] ;
int W[MAXN], Wt[MAXN] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline void Add(int F, int T) {
	E[++ Tot].F = F ; E[Tot].T = T ;
	E[Tot].Next = H[F], H[F] = Tot ;
}

struct TREE {
	int L, R, Sum, Tag ;
}	G[MAXN << 1] ;
inline void Push_Up(int Now) {
	G[Now].Sum = (G[LS].Sum + G[RS].Sum) % Mod ;
}

inline void Push_Down(int Now) {
	if (G[Now].Tag) {
		G[LS].Tag += G[Now].Tag ; G[RS].Tag += G[Now].Tag ;
		(G[LS].Sum += G[Now].Tag * (G[LS].R - G[LS].L + 1)) %= Mod ;
		(G[RS].Sum += G[Now].Tag * (G[RS].R - G[RS].L + 1)) %= Mod ;
		G[Now].Tag = 0 ;
	}	return ;
}

inline void Build_Tree(int Now, int L, int R) {
	G[Now].L = L ; G[Now].R = R ;
	if (G[Now].L == G[Now].R) {
		G[Now].Sum = V[L] ;
		if (G[Now].Sum > Mod) G[Now].Sum %= Mod ;
		return ;
	}
	Build_Tree(LS, L, Mid), Build_Tree(RS, Mid + 1, R) ;
	Push_Up(Now) ;
}

inline void SegChange(int Now, int L, int R, int K) {
	if (G[Now].L >= L && G[Now].R <= R) {
		G[Now].Sum += K * (G[Now].R - G[Now].L + 1) ;
		G[Now].Tag += K ;
		return ;
	}	Push_Down(Now) ;
	if (L <= E_Mid) SegChange(LS, L, R, K) ;
	if (R > E_Mid)  SegChange(RS, L, R, K) ;
	Push_Up(Now) ;	return ;
}

inline int Query(int Now, int L, int R) {
	if (G[Now].L >= L && G[Now].R <= R)
		return G[Now].Sum % Mod ;
	Push_Down(Now) ; int Ans = 0 ;
	if (E_Mid >= L) Ans = Ans + Query(LS, L, R) % Mod ;
	if (E_Mid < R)  Ans = Ans + Query(RS, L, R) % Mod ;
	return Ans % Mod ;
}

int Deep[MAXN], Fa[MAXN], Size[MAXN], Son[MAXN] ;
inline void Dfs1(int Now, int Fas, int Deeps) {
	Deep[Now] = Deeps, Fa[Now] = Fas, Size[Now] = 1 ;
	int Maxson = - 1 ;
	for (int i = H[Now] ; i ; i = E[i].Next) {
		if (E[i].T == Fas) continue ;
		Dfs1(E[i].T, Now, Deeps + 1) ;
		Size[Now] += Size[E[i].T] ;
		if (Size[E[i].T] > Maxson)
			Son[Now] = E[i].T, Maxson = Size[E[i].T] ;
	}
}

int Id[MAXN], Top[MAXN], Cnt ;
inline void Dfs2(int Now, int Tops) {
	Id[Now] = ++ Cnt, V[Cnt] = W[Now], Top[Now] = Tops ;
	if (! Son[Now]) return ;
	Dfs2(Son[Now], Tops) ;
	for (int i = H[Now] ; i ; i = E[i].Next) {
		if (E[i].T == Fa[Now] || E[i].T == Son[Now])
			continue ;
		Dfs2(E[i].T, E[i].T) ;
	}
}

inline int Range(int X, int Y) {
	int Ans = 0 ;
	while (Top[X] != Top[Y]) {
		if (Deep[Top[X]] < Deep[Top[Y]] ) swap(X, Y) ;
		int Res = Query(1, Id[Top[X]], Id[X]) ;
		Ans = (Ans + Res) % Mod ; X = Fa[Top[X]] ;
	}
	if (Deep[X] > Deep[Y]) swap(X, Y) ;
	int Res = Query(1, Id[X], Id[Y]) ;
	Ans += Res ; return Ans % Mod ;
}

inline int GetSon(int Now) {
	return Query(1, Id[Now], Id[Now] + Size[Now] - 1) % Mod ;
}

inline void Change(int X, int Y, int K) {
	K %= Mod ;
	while (Top[X] != Top[Y]) {
		if (Deep[Top[X]] < Deep[Top[Y]]) swap(X, Y) ;
		SegChange(1, Id[Top[X]], Id[X], K) ;
		X = Fa[Top[X]] ;
	}
	if (Deep[X] > Deep[Y]) swap(X, Y) ;
	SegChange(1, Id[X], Id[Y], K) ;
}

inline void Point(int Now, int K) {
	SegChange(1, Id[Now], Id[Now] + Size[Now] - 1, K % Mod) ;
}

int main() {
	N = Read() ; M = Read() ; Root = Read() ; Mod = Read() ;
	for (int i = 1 ; i <= N ; i ++) W[i] = Read() ;
	for (int i = 1 ; i <  N ; i ++) {
		int A = Read(), B = Read() ;
		Add(A, B) ; Add(B, A) ;
	}
	Dfs1(Root, 0, 1) ; Dfs2(Root, Root) ; Build_Tree(1, 1, N) ; 
	for (int i = 1 ; i <= M ; i ++) {
		int Opt = Read(), X, Y, Z ; switch (Opt) {
			case 1: X = Read(), Y = Read(), Z = Read(), Change(X, Y, Z) ; break ;
			case 2: X = Read(), Y = Read(), printf("%d
", Range(X, Y)) ; break ;
			case 3: X = Read(), Z = Read(), Point(X, Z) ; break ;
			case 4: X = Read(), printf("%d
", GetSon(X)) ; break ;
		}
	}	return 0 ;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/sue_shallow/p/TCS.html