BessieTheCow's blog

By BessieTheCow, 5 weeks ago, In English,

I remember seeing people mention that link cut trees can be used for dynamic LCA queries, but I can't find any information on how its done. One way that I can think of to find the LCA of nodes $$$u$$$ and $$$v$$$ is to access $$$u$$$ first and then $$$v$$$, then splay $$$u$$$ and take its path parent pointer. Is there a more efficient way? Also, can link cut trees be used for subtree aggregate queries?

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

»
5 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Hi Bessie,

The way you described to get LCA is exactly how I do it. That is 2*log(n), and the splay(u) is pretty much O(1). I don't think you can get much better than that, even by that large of a constant factor.

On subtree aggregates: Sometimes they LCTs can maintain them, it depends on exactly what the aggregate is. If it is something like sum or xor, then yes they can. If it is something like max or min, I believe it will cost you a second log factor, but you can still do it better than n^2. It also becomes very cancer and I would recommend rethinking the solution at that point.

I hope you and Farmer John are doing well, David