树链剖分 学习笔记

发表于
非常简单的树剖板子介绍

解决问题

修改树上某一路径的权值，查询树上某一路径（子树）的权值。

基本思想

将树上的结点分成若干重链，每次只用维护重链即可。

算法步骤

1.两次DFS，分别预处理出{father,dep,size,son}和{top,seg,rev}；

2.建线段树；

3.修改&求值

DFS细节

第一次DFS没啥细节。

第二次注意在DFS前先处理根节点。对于每个结点先走重儿子，保证线段树中重链连续；然后处理其他儿子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs2(int u){
	if(son[u]){
		seg[son[u]]=++seg[0];
		top[son[u]]=top[u];
		rev[seg[0]]=son[u];
		dfs2(son[u]);
	}
	for(int i=lst[u];i;i=e[i].lst){
		int v=e[i].t;
		if(!top[v]){
			seg[v]=++seg[0];
			rev[seg[0]]=v;
			top[v]=v;
			dfs2(v);
		}
	}
}

修改细节

对于每条路径的两个结点，若不在同一条重链上，则选取深的重链往上跳；最后更新当前重链。

1
2
3
4
5
6
7
8
9
10
11
void modify(int x,int y,int v){
	int fx=top[x],fy=top[y],ret=0;
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
		mfy(1,seg[fx],seg[x],v);
		x=fath[fx];
		fx=top[x]; 
	}
	if(seg[x]>seg[y])swap(x,y);
	mfy(1,seg[x],seg[y],v);
}

询问细节

大体流程与修改相同，代码略。