Блог пользователя rajkumar62506

Автор rajkumar62506, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by rajkumar62506 (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Yes, Using RMQ tables is O(1) because you divide the range L..R at some inner point say M and query(L..M) and query(M..R) [Here the L..M and M..R can overlap] and take the minimum of those two to get the LCA. This is fine for minimum (and hence to get LCA) as overlap does not matter.

But the same, cannot be done for other operations like sum, or etc. To do these operations we need to divide L..R in exclusive non-overlapping intervals which binary lifting does in O(log n).

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

I see you're using a log2 array, but it's not actually needed. I think this will be slightly faster: 31-__builtin_clz(n-1) will give the largest k such that 2^k <= n.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Since there will almost never be any update to the stored values, a Sparse Table might be a better choice, allowing O(1) query answering with O(NlogN) build time.
https://cp-algorithms.com/graph/lca.html.

This is usually my go-to (the Sparse Table in my library is prewritten for this), but binary lifting also allows you to access the K-th ancestor of any node.