The Story of Joon

Link/Cut Tree (2) 다음 자료들을 참고했다. * 위키피디아 링크 * MIT Lecture Note Link/Cut Tree를 이해하거나 구현하기 위해서는 먼저 Splay Tree에 대한 이해가 필요하다. Splay Tree에 대한 내용은 여러 곳에 잘 설명되어 있다. Link/Cut Tree는 여러 개의 트리를 관리하는 자료구조이다. 이 자료구조의 특징은, find_root(노드가 속한 트리의 루트), link(한 트리의 루트를 다른 트리의 노드로 연결), cut(루트가 아닌 노드와 부모 사이의 연결 제거) 연산을 모두 amortized $O(\log N)$의 복잡도에 수행이 가능하다는 것이다. 앞서 말했듯이 LCT는 여러 개의 트리로 되어있는데, 이 각각의 트리를 represented tr..

cubelover님의 블로그를 많이 참고했다. Splay Tree에 대한 설명은 이 블로그로 가면 많은 도움이 된다.#include #ifdef TOPOLOGY#define debug(...) fprintf(stderr, __VA_ARGS__)#else#define debug(...)#endifusing namespace std;template >class splay_tree {public: class node { public: node *p, *l, *r; T key; int cnt; node() { p = l = r = NULL; key = T(); } node(T k) { p = l = r = NULL; key = k; } node(T k, node *np) { l ..