Problem Solving/Algorithm
-
Fragmented TreeProblem Solving/Algorithm 2023. 9. 3. 21:43
Codeforces를 돌아다니다가 흥미로운 글을 하나 읽었다. Sqrt Fragmented Tree라는 자료구조로, 글 자체는 7년 전의 것이지만 한국에서 잘 알려지지 않았기에 설명하는 글을 작성한다. Approach 업데이트가 있는 트리 DP는 Centroid Decomposition Tree나, Euler Tour Trick과 HLD를 사용한 소위 Dynamic Tree DP등을 통해서 할 수 있음이 알려져 있다. 물론, 이러한 자료구조들은 구현이 어렵고, 최소한의 생각을 해야 문제가 풀리기 때문에 머리가 아프다. 트리에서 Square Root Decomposition을 사용할 수 있을까라는 생각을 해본 적이 있을 것이다. 트리는 connected component로 나누면 component의 크기 ..