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

摘要

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