最近公共祖先算法在管道运输的应用

• 作者: 彭诗怡 郭煜锐 黄检宝
• 来源期刊: 现代计算机
• 关键词: 最近公共祖先 欧拉序 ST表 树上差分
• 年，卷（期）: 2020,（25）
• 所属期刊栏目: 研究与开发
• 页码范围: 37-40
• 页数: 4页
• 语种: 中文
• DOI: 10.3969/j.issn.1007-1423.2020.25.007

摘要

介绍最近公共祖先算法的原理和应用,并总结四种最近公共祖先算法:欧拉序结合ST表法、倍增法、并查集结合Tar?jan算法和树链剖分法,重点剖析欧拉序结合ST表法具体的算法过程.提出数列区间操作问题的解决方案,并将此推广在树中,讨论两种树链操作方式:树上差分和相对于根结点的树上标记法.将最近公共祖先算法与树上标记结合,并运用在管道运输问题上,能在O(n log2n)的算法复杂度下,监控管道运输网络的最大压力值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄检宝		4	0	0.0	0.0
2	彭诗怡		1	0	0.0	0.0
3	郭煜锐		1	0	0.0	0.0