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

Application of Lowest Common Ancestors in Pipeline Transport

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

Introduces the principle and application of the lowest common ancestor algorithm,and summarizes four lowest common ancestor algo⁃rithms:Euler order combined with ST table method,multiplication method,union-find algorithm combined with Tarjan algorithm and tree chain division method,focusing on analyzing the specific algorithm process of Euler order combined with ST table method.This paper pres⁃ents a solution to the problem of sequence interval operation and extends it to trees.Two kinds of tree chain operation methods are dis⁃cussed:difference of nodes in tree method and tree marking method relative to root node.By combining the recent common ancestor algo⁃rithm with tree marking method and applying it to pipeline transportation problem,the maximum pressure value of pipeline transportation network can be monitored under O(n log2n)algorithm complexity.