Is this O(1) LCA query sol is correct?

Revision en2, by rajkumar62506, 2020-08-18 04:21:50

Hello Everyone,

There are many solutions for LCA query,like simple O(N) by traversal only,O(log(N)^2) using Binary lifting + Binary Search,Also most famous O(log(N)) solution. But recently I when I was learning about sparse table, I accounted with O(1) sol for each query using Euler Tour+RMQ using Sparse table. I tried to submit sol using this on SPOJ and CSES problem set and got accepted.

SPOJ Submission
CSES Submission

Now I have only one doubt that is this O(1) solution has any flaw?

If yes,what?

And if not,as far as I know this sol is not so famous compared to log(N) sol,why? even it is easy to code.It might possible that it is famous but I didn't know that.

Tags #lca, #rmq, o(1), #eule walk


  Rev. Lang. By When Δ Comment
en2 English rajkumar62506 2020-08-18 04:21:50 12 Tiny change: 'uler Tour+Sparse tab' -> 'uler Tour+RMQ using Sparse tab'
en1 English rajkumar62506 2020-08-18 04:10:53 5490 Initial revision (published)