Euler tour technique 이란 트리를 전위 탐색(부모 -> 자식)으로 넘버링 해서 트리를 관리하는 테크닉이다.
이러한 방식으로 트리를 관리하면 트리에서 임이의 서브트리에 대한 쿼리를 쉽게 처리할 수 있다.
트리에 전위 탐색으로 넘버링을 하고, 임의의 노드에 대해 생각해보다.
이 노드를 루트로 하는 서브트리 내에 속하는 모든 정점들은 인접하고 연속하게 넘버링이 되어있다는 것을 알 수 있다.
다음의 사진을 보자. (검정 : node number, 파랑 : 전위 탐색으로 넘버링 된 수)
여기서 2를 루트로 하는 서브트리 내의 모든 정점들에 대해 넘버링 된 수들을 나열해 보면 2, 3, 4, 5, 6 으로 연속한 것을 알 수 있다.
이러한 특성 때문에 오일러 투어 테크닉과 세그먼트 트리 같은 자료구조를 사용해서 서브트리 내에서 최댓값을 찾는 등의 문제들을 해결할 수 있다.
'PS' 카테고리의 다른 글
Mo's Algorithm (0) | 2023.08.14 |
---|---|
Sqrt Decomposition (0) | 2023.08.13 |
Master Theore (0) | 2023.08.11 |
단절점 (0) | 2023.08.11 |
monotone queue (0) | 2023.08.05 |