rajkumar62506's blog

Is this O(1) LCA query sol is correct?
By rajkumar62506, history, 4 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Absolutely right.Sparse Table is good for idempotent functions,like min,max,gcd,lcm etc.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok.I will try this. Thnx for knowledge.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Actually there is an even simpler way to do this, just use the __lg() function.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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.

→ Reply