前言
树链剖分是一个很好用的处理树上统计信息的方法,大致思想就是把树上路径分成$log N$条链,再用线段树之类的数据结构维护一下,所以时间复杂度得到了保障
怎么做
个人认为这篇讲的很好:
https://www.cnblogs.com/George1994/p/7821357.html
注意
debug树链剖分对于我来说真是个痛苦的过程,初学时一个错误查了近一个小时才查出来.
首先你要知道线段树上序列是什么?
他们是$dfs_2$中的每个树节点的$dfs$顺序存在$dfn[]$中,$rnk[]$则记录对应$dfn[]$对应的节点编号,这点千万不要搞错,尤其在单点操作时极其容易忽略
build函数
1 |
|
必要的操作(一定要检查是否写了)
1 |
|
例题
例题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
代码: 请戳这里
简要题解:区间覆盖