AzorAhai's blog

dynamic graph / lca using treaps ?
By AzorAhai, history, 9 years ago, In English

Hi guys Can someone please give me a good resource of how to solve dynamic graph connectivity and dynamic lca using treaps or how to implement link cut trees using treaps .. i can not find any good resources for that. thanks in advance guys.

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

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AzorAhai (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

I just googled 'link cut tree' and the 3-rd link was a full paper by authors XD.

Well, from my expirience, start from link cut, cause full dina-conn has MUCH more complicated concept/implementation.

Btw u can just ask this guy Darooha directly, its Daniel Sleator, the one who invented Splay-trees and had done a lot of work in link-cut trees.

(Hint: u can use treaps instead of splay and get O(log^2) instead of O(Log) per query, but Darooha's papers use Splay)

P.S. Englando is dead

→ Reply