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

Автор SecondThread, история, 5 лет назад, По-английски

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?

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

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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