算法学习笔记(6): 树链剖分
树链剖分
树链剖分是一个很神奇,但是在树上可以完成一些区间操作问题
简单来说,就是把一棵树分成一条条的链,通过维护链上的信息来维护整棵树的信息
基础知识可以参考我的另外一篇博客:算法学习笔记(5): 最近公共祖先(LCA)
这里假设你已经掌握了上述博客中的所有相关知识,并清晰了其背后的原理
性质?发现?
当我们动手模拟寻找dfn
的步骤时,我们不难发现,同一条链上的dfn
序是连续的
意味着我们可以通过结点的dfn
序来维护其信息
由于涉及到区间修改或者查询之类的问题,一般来说需要用到线段树的辅助
如果不明白线段树的话,建议不要食用本文
具体用法
我们以模板题:【模板】轻重链剖分/树链剖分 - 洛谷为例
由于我们需要修改两个点的路径上点的权值,依据上文我们已经知道在链上的dfn
序是连续的,很明显,我们需要找到两个点路径之间所有在同一条链上的部分进行区间修改
联想到树链剖分求LCA的过程,我们只需要在两个点向上跳的时候顺便维护其信息即可
类C伪代码可以参考如下
void change(int x, int y, data...) {
// 不在同一条链上!
while (top[x] != top[y]) {
// 保证top较低的点先跳,防止跳飞
if (dep[top[x]] < dep[top[y]]) swap(x, y);
modify(dfn[top[x]], dfn[x], data...);
x = fa[top[x]];
}
// 保证x的dfn较小
if (dep[x] > dep[y]) swap(x, y);
modify(dfn[x], dfn[y], data...);
}
modify(x, y, data...)指的是根据data维护区间
[x, y]
上的信息
注意:如果使用了线段树,在建树的时候一定要注意初始值。我指的是点dfn[x]
上的值才是x
的初始值。
如果你发现你似乎需要写两个
change
函数,但是你又没想到可以替代的名字可以采用把线段树的代码用namespace包含进去(我常用seg作为namespace的名字,下文我会沿用这个名字)
具体来说,例如:
namespace seg { 线段树要的数据...; void build(...) { ... } void change(...) { ... } void query(...) { ... } .... }
在namespace之外,就可以采用
seg::change(...)
之类没有歧义的写法了这样很好的避免了
词汇匮乏命名混乱的问题
复杂度:自然还是要分析一波。由于树链剖分最多会分成logN
个区间,每个区间的操作基于线段树区间修改的复杂度,所以复杂度为(O(Nlog^2N))
这个部分……讲的好少啊
管他的,下课!
相关文章
- 项目管理软件KanbanFlow、Trello与nTask大比拼
- 一篇文章带你了解CSS Pseudo-classes(伪类 )
- 比看书还高效,这4种提高编程技能的方式你知道么?
- 线程安全性详解(原子性、可见性、有序性)
- 如何在 .NetCore 中使用 AutoMapper 高级功能
- k8s部署高可用配置中心apollo-手动验证成功
- 中亦科技举办图谱技术线上交流活动 助力金融业数字化转型发展
- 线程不是你想中断就能中断
- 深耕软件行业45年,这位「老前辈」在退休之际分享了他的职业感悟
- 分布式 PostgreSQL 集群(Citus)官方安装指南
- 使用GitLabCI实现 多模块项目CI/CD
- Redis+Caffeine两级缓存,让访问速度纵享丝滑
- 关于Dubbo随便问八个问题
- Spring中这些能升华代码的技巧,可能会让你爱不释手
- 软技能:使用四象限法分析一切问题
- 展望2021,DevOps与敏捷方法不再“相爱相杀”
- 手把手教你用Go语言打造一款简易TCP端口扫描器
- 互联网系统架构为什么要做前后端分离呢?
- 程序员如何写出高质量的代码程序
- API快速开发平台设计思考