알고리즘/그래프
2021. 8. 25.
HLD
트리의 경로에 관한 질의를 빠르게 처리할 수 있게 해주는, Heavy-Light Decomposition (HLD)에 대해 알아봅시다. 이전에 트리의 모든 서브트리를 하나의 구간으로 나타내게 해주는 Euler tour technique에 대한 글을 쓴 적이 있습니다. https://anz1217.tistory.com/41 Euler tour technique 트리를 펴서 배열에 저장해봅시다. 다음과 같은 트리가 있다고 가정해봅시다. 1번 정점이 루트입니다. 이 트리에서 루트인 1번 정점부터 시작해 DFS를 돌립니다. 그리고 각 정점이 방문되는 순서 anz1217.tistory.com 이와 비슷하게 트리의 모든 경로도 HLD를 이용하면 몇 개의 구간으로 나눌 수 있고, 세그먼트 트리등의 자료구조를 사용할 ..
