Since there are many ways to find LCA(lowest common ancestor) with different preprocessing and query time, and almost each one is able to pass the time limit in general case, I was wondering which method is generally used among competitive programmers. I mean there must be one among them which is having a slight edge over the others in terms of code length, etc., and is widely used.
So my question is that which technique to find LCA is mostly used in competitive programming.
I think the binary lifting approach is mostly used to find LCA. Though it has a query time of log(N) but the RMQ reduction has a high constant factor i guess (as one of my codes TLED even after using that and got AC later by replacing the work of lca.) But there are a few other interesting approaches as mentioned here and here . Now it depends on you which one you find comfortable coding up. I prefer bnary lifting so I use it almost everywhere.
I would say, go for binary lifting using sparse table. It has memory complexity O(NmaxBits) and pre-processing O(NmaxBits), having query time O(maxBits), with a low constant factor as i believe.
@Soham1234 though I know LCA, but hearing of Binary Lifting for the first time, would be nice of you, if you could post tutorial on your blog. Thank you.
Here you go. Hackerrank Tutorial, [Topcoder Tutorial][2], Check for the O({<}NlogN,logN{>}), method in these tutorials
[2]: Topcoder