Link Cut Tree implementation

Revision en4, by bicsi, 2020-12-21 12:56:13

Hello!

Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.

The implementation is here:

Implementation

It is around 100 lines long (which is not ideal), but it has some neat features. For example, if you call lc.Path(a, b), the implementation will return the root of a splay tree node which contains the whole path from a to b. Also, the function access(v) will make sure that node v's splay tree would contain the whole path from the root at that time to v. It also allows subtree query via the (amazing) trick of virtual subtrees (https://codeforces.me/blog/entry/67637).

I feel like there is no implementation with a very clean way of modifying it (for the people who don't know LCT), so I decided to adapt one myself (also, I don't like using raw pointers -- if you're like me, you might enjoy this implementation). Also, another thing that I like about this implementation is that the splay tree code is independent to the fact that it's used inside a link-cut tree (it's just plain splay tree code, which can be extracted away).

Another thing that is very useful in my opinion is that the splay tree can be used completely separated from the link cut tree (it is not embedded in its implementation), so they could go into separate snippets in your ICPC notebooks.

In order to adapt the implementation to path aggregates (updates/queries of any type), you would have to create some function that updates/queries the splay tree node GetPath(u, v) and to potentially modify the push and pull methods (push is lazy propagation, whereas pull is regular tree update from children).

Also, here is a pastebin of a strees test code, in case you want to test the implementation.

Any thoughts on how to improve the implementation? What do you think about it overall?

Tags #advance data structures, splay tree, implementation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English bicsi 2020-12-21 12:56:13 2675
en3 English bicsi 2020-04-11 23:38:39 14 Tiny change: 'tebin.com/UBKL5T0t), in case' -> 'tebin.com/BhdfucH6), in case'
en2 English bicsi 2020-04-11 23:37:37 134 Tiny change: 'l way.\n\n[Also, her' -> 'l way.\n\n#### [Also, her'
en1 English bicsi 2020-04-11 23:35:48 4025 Initial revision (published)