RMQ : Best Time Complexity

rmq
segment-tree
sparse-tables

#1

What is the best time complexity one can achieve in finding LCA using RMQ(Static)??

I know RMQ using Sparse Table==>Preprocessing Time: O{NlogN) Query:O(1)

Segment Tree.Preprocessing Time: O{N) Query:O(logN).

Is there method with preprocessing time O(N) and Query : O(1)??


#2

here it is:https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#A%20O(N),%20O(1)%20algorithm%20for%20the%20restricted%20RMQ