前言

树链剖分是一个很好用的处理树上统计信息的方法,大致思想就是把树上路径分成$log N$条链,再用线段树之类的数据结构维护一下,所以时间复杂度得到了保障

怎么做

个人认为这篇讲的很好:

https://www.cnblogs.com/George1994/p/7821357.html

注意

debug树链剖分对于我来说真是个痛苦的过程,初学时一个错误查了近一个小时才查出来.

首先你要知道线段树上序列是什么?

他们是$dfs_2$中的每个树节点的$dfs$顺序存在$dfn[]$中,$rnk[]$则记录对应$dfn[]$对应的节点编号,这点千万不要搞错，尤其在单点操作时极其容易忽略

build函数

1
2
3
4
5
6
7
8
9
10
11
12

   void build(int now,int l,int r){
if(l==r){
	mx[now]=sum[now]=w[rnk[l]];//注意是rnk[l]
	return ;
}
int mid=(l+r)>>1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
sum[now]=sum[now<<1]+sum[now<<1|1];
   mx[now]=max(mx[now<<1],mx[now<<1|1]);
return ;
   }

必要的操作(一定要检查是否写了)

1
2
3
4

   dep[1]=1,fa[1]=0;//假设root是1
dfs_1(1);
dfs_2(1,1);
build(1,1,n);

例题

例题1：

https://www.luogu.org/problemnew/show/P2590

代码:请戳这里

简要题解: 无

例题2:

https://www.luogu.org/problemnew/show/P3384

代码: 请戳这里

简要题解: 无

例题3:

https://www.luogu.org/problemnew/show/P3950

代码及题解:

https://www.cnblogs.com/Rye-Catcher/p/9351619.html

例题4:

https://www.luogu.org/problemnew/show/P4092#sub

这道题比较有意思，题解中找目标所在重链然后倍增的思路在今年NOI中可以运用

代码及题解:

https://www.cnblogs.com/Rye-Catcher/p/9275770.html

例题5:

查了好久的错…

https://www.luogu.org/problemnew/show/P2146

代码: 请戳这里

简要题解:区间覆盖