radoslav11's blog

By radoslav11, history, 2 months ago, In English,

Hello!

Recently I relearned link cut trees and now I'm curious how to do subtree updates/queries as I have seen comments in the past that it's possible. So can someone share how to do it and also can we perform both subtree and path queries/updates simultaneously?

Also can someone share some interesting (and hard) problems with link cut trees which you have encountered and liked.

Thanks in advance! :)

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

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

For subtree queries, check this blog: Memphis's Blog

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can only do path queries with LC-T, for subtree queries use Euler tree.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If I didn't misunderstood anything, it seems like a simple modification of euler tour technique — If you imagine an euler tour sequence of length 2N-2, subtree queries are subsegment queries, and link / cut operations corresponds to a subsegment splicing / merging. Thus everything can be done with a splay tree.

There is an awesome practice problem here, where you have 12 kind of queries, yay!!!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But then how to answer path queries (I was curious if it was possible to do both subtree and path queries)?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      So I really misunderstood something, sorry :/