DSU (1) 썸네일형 리스트형 Path Comprssion DSU의 amortized O(logN) 증명 Weighted union rule, Path compression 중 하나만 사용하면 amotized \(O(logN)\), 둘 모두를 사용하면 amortized \(O(\alpha(N))\)임이 잘 알려져있습니다. Path compression만을 사용했을 때 시간복잡도의 증명은 한글 자료가 잘 없는 것 같아 작성합니다. Heavy Light Decomposition스러운 논리를 사용합니다. 정점 u가 v의 자식일 때 sz[v] \(\leq\) sz[u] / 2이면 u->v간선은 light edge, 나머지는 heavy edge라고 해봅시다. 당연하게도 heavy edge는 정점당 하나만 생깁니다 (sz[x] := x의 서브트리의 크기) 임의의 정점 (u, v)에 대해 u->v로 가는 경로는 최대 \.. 이전 1 다음
