论文标题
更简单的O（1）查询祖先的查询算法
Simpler O(1) Query Algorithm for Level Ancestors
论文作者
论文摘要
本说明描述了一种非常简单的O（1）查询时间算法，用于查找水平祖先。这基本上是伯克曼和维斯金（O.Berkman and U.Vishkin）平行算法的序列（重新） - 实现，在树木中找到了水平 - 熟悉的人，JCSS，48，214---230，1994）。 尽管基本算法的预处理时间为O（n log n），但通过具有其他级别或使用表格查找，可以将预处理时间缩短为几乎是线性或线性。 表格查找算法可以用$ n $处理器在O（1）并行时间内构建，还可以用来简化Berkman和Vishkin的并行算法，并使其最佳。
This note describes a very simple O(1) query time algorithm for finding level ancestors. This is basically a serial (re)-implementation of the parallel algorithm of Berkman and Vishkin (O.Berkman and U.Vishkin, Finding level-ancestors in trees, JCSS, 48, 214--230, 1994). Although the basic algorithm has preprocessing time of O(n log n), by having additional levels or using table lookup, the preprocessing time can be reduced to almost linear or linear. The table lookup algorithm can be built in O(1) parallel time with $n$ processors and can also be used to simplify the parallel algorithm of Berkman and Vishkin and make it optimal.
