A Linear Approach to LCA¶

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

In this approach, we divide the array into chunks of size \(\frac{\lg(n)}{2}\). Since the difference between any two consecutive elements is exactly 1, this array can have at most \(2^{\frac{\lg(n)}{2}} = \sqrt{n}\) possible structural states. For each of these sub-intervals, we precompute the minimum element, which with a good implementation will result in \(O(\sqrt{n} \cdot \lg^2(n))\) time and memory complexity. For each interval, we also determine which of the \(\sqrt{n}\) possible states it resembles. This step can also be done in linear time.

Next, we treat each chunk as an element of a new array and build a sparse table over it, similar to what we discussed in the previous section. This step can be done in \(O\left(\frac{2n}{\lg(n)} \cdot \lg\left(\frac{2n}{\lg(n)}\right)\right) = O(n)\) time.

Now, let’s address how to answer queries. Consider a given range. It either falls entirely within one of the small chunks (whose answer we have precomputed) or spans across partial chunks. For the middle chunks that lie entirely within the range, compute their minimum using the prebuilt sparse table. For the partial chunks at the start and end of the range, handle them as in the first case. Finally, compute the minimum among these three candidates. This minimum will be the answer.