SecondThread's blog

By SecondThread, history, 5 years ago, In English

I'm somewhat familiar with how Link Cut Trees work. I have watched Erik Demaine's lecture on them from MIT Open Courseware, solved a couple problems that use them with my team's (very copy-pasteable) book code, and read about them a bit, so I have an idea of how they work in general.

The code I have used supports range path update, path query, link, cut, and checkConnected queries. I read on Wikipedia that Euler Tour Trees are better for subtree queries and link cut trees are better for path queries. However, I looked through ko_osaga's code for fully dynamic connectivity and it looks like he is using a splay tree or link-cut tree of some sort. Link-cut trees use splay trees to store preferred paths, so the size of a splay tree node's subtree doesn't really mean anything, right? But for the dynamic connectivity problem he was trying to solve, I'm pretty sure you need to check, after cutting an edge, which of the trees you created is smaller. That sure doesn't seem like a path operation to me.

So is it possible to do subtree-like operations on LCT's?

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

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

What I used is called Euler-tour tree, and is not related to LCT at all.

Basically, if you want to handle some queries on tree, you can use HLD for path, Euler tour labeling for subtree. LCT and ETT are the data structures corresponding to first/second options. Compared to LCT, the idea for ETT is very simple: If you are changing the tree by add/removing edges, the corresponding subtree forms an interval, and thus the Euler tour can be maintained by any kind of BBSTs.

The implementation is actually quite complicated than what it sounds, but I think this should help.

I think, using top-trees can help supporting path and subtree queries simultaneously. (Link-Cut Memphis in China seems related, but tbh I don't know both of them)

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

update: This is actually possible, as described in this blog. Thanks to RobeZH for showing me!