LowestCommonAncestorStaticRmq (JGAlgo - Parent 0.5.1-SNAPSHOT API)

java.lang.Object
- com.jgalgo.alg.tree.LowestCommonAncestorStaticAbstract
- - com.jgalgo.alg.tree.LowestCommonAncestorStaticRmq

All Implemented Interfaces:

LowestCommonAncestorStatic
```
public class LowestCommonAncestorStaticRmq
extends LowestCommonAncestorStaticAbstract
```
Static LCA implementation using RMQ.
By traversing the tree once and assigning for each vertex a number corresponding to its depth, the LCA query is equivalent to a range minimum query. This RMQ problem is a special case of RMQ, as the different between any pair of consecutive elements is always +1/-1, and RmqStaticPlusMinusOne can be used.
The algorithm require preprocessing of \(O(n)\) time and space and answer queries in \(O(1)\) time.
Based on 'Fast Algorithms for Finding Nearest Common Ancestors' by D. Harel, R. Tarjan (1984).

Author:

Barak Ugav

- Nested Class Summary
  - Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.LowestCommonAncestorStatic
    LowestCommonAncestorStatic.IDataStructure
- Constructor Summary
  
  Constructors
  Constructor Description
  
  LowestCommonAncestorStaticRmq()
  Create a new static LCA algorithm object.
- Method Summary
  - Methods inherited from class com.jgalgo.alg.tree.LowestCommonAncestorStaticAbstract
    preProcessTree
  - Methods inherited from class java.lang.Object
    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - LowestCommonAncestorStaticRmq
```
public LowestCommonAncestorStaticRmq()
```
    Create a new static LCA algorithm object.
    Please prefer using LowestCommonAncestorStatic.newInstance() to get a default implementation for the LowestCommonAncestorStatic interface.