LCA Linear Time Solution¶

In the previous section, we saw how LCA and RMQ problems can be converted into one another. If you notice, when converting LCA to RMQ, an array is constructed where the difference between adjacent elements is exactly one. We solve this specific problem in linear time, which implies that LCA and RMQ are also solved in \(O(n+q)\) time. Note that this approach has theoretical value but is not used in practice due to implementation complexity and high constant factors.

In this approach, we divide the array into blocks of size \(\frac{lg(n)}{2}\). Since the difference between any two consecutive elements is exactly 1, this array can have a total of \(2^{\frac{lg(n)}{2}} = \sqrt{n}\) possible structural types. For each sub-interval corresponding to these types, we find the minimum element, which, with good implementation, will have a time and space complexity of \(O(\sqrt{n} * lg^2(n))\). For each block, determine which of the possible types it resembles. This can also be done in linear time. Then, treat each block as an element in a new array and build a sparse table on it, similar to what we discussed in the previous section. This can also be done in \(O(\frac{2*n}{lg(n)}*lg(\frac{2*n}{lg(n)})) = O(n)\) time.

Now, we want to answer queries. Consider an interval. It either falls entirely within one of the small blocks, in which case we have precomputed its answer, or its start is within one block and its end is within another block. For the middle blocks that fall entirely within the interval, compute their minimum element using the sparse table we built. For the two end blocks (start and end), proceed as in the first case. Then, compute the minimum element among these three candidates. This element is your answer.