무거운 경로 분해(HLD) 계산기
트리를 무거운 간선으로 이어 몇 개의 체인으로 쪼개고, 두 정점 사이의 경로가 어느 체인 조각들로 나뉘는지 보여 줍니다. 가벼운 간선을 탈 때마다 서브트리가 반 이하로 준다는 것을 실제로 재어 O(log n)임을 확인할 수 있습니다.
v번째 값이 v의 부모입니다. 뿌리는 −1. 정점 2000개까지
15번에서 22번까지의 경로
체인 4조각
경로 위 정점은 7개, 최소 공통 조상은 1번입니다. 완전탐색으로 구한 경로와 같습니다.
경로가 나뉜 조각
| # | 체인 머리 | 배열 구간 | 정점 |
|---|---|---|---|
| 1 | 0 | [1, 4] | 1 → 3 → 7 → 15 |
| 2 | 4 | [9, 9] | 4 |
| 3 | 10 | [13, 13] | 10 |
| 4 | 22 | [15, 15] | 22 |
조각마다 배열의 «연속 구간»이라는 것이 요점입니다. 그래서 세그먼트 트리를 얹으면 조각 하나를 O(log n)에 답할 수 있고, 조각이 O(log n)개라 전체가 O(log² n)이 됩니다.
이 트리의 모습
만들어진 체인
| 머리 | 길이 | 정점 (위 → 아래) |
|---|---|---|
| 0 | 5 | 0 → 1 → 3 → 7 → 15 |
| 16 | 1 | 16 |
| 8 | 2 | 8 → 17 |
| 18 | 1 | 18 |
| 4 | 3 | 4 → 9 → 19 |
| 20 | 1 | 20 |
| 10 | 2 | 10 → 21 |
| 22 | 1 | 22 |
| 2 | 4 | 2 → 5 → 11 → 23 |
| 24 | 1 | 24 |
| 12 | 2 | 12 → 25 |
| 26 | 1 | 26 |
| 6 | 3 | 6 → 13 → 27 |
| 28 | 1 | 28 |
| 14 | 2 | 14 → 29 |
| 30 | 1 | 30 |
정점마다
| v | 부모 | 서브트리 | 무거운 자식 | 체인 머리 | 배열 위치 |
|---|---|---|---|---|---|
| 0 | 뿌리 | 31 | 1 | 0 | 0 |
| 1 | 0 | 15 | 3 | 0 | 1 |
| 2 | 0 | 15 | 5 | 2 | 16 |
| 3 | 1 | 7 | 7 | 0 | 2 |
| 4 | 1 | 7 | 9 | 4 | 9 |
| 5 | 2 | 7 | 11 | 2 | 17 |
| 6 | 2 | 7 | 13 | 6 | 24 |
| 7 | 3 | 3 | 15 | 0 | 3 |
| 8 | 3 | 3 | 17 | 8 | 6 |
| 9 | 4 | 3 | 19 | 4 | 10 |
| 10 | 4 | 3 | 21 | 10 | 13 |
| 11 | 5 | 3 | 23 | 2 | 18 |
| 12 | 5 | 3 | 25 | 12 | 21 |
| 13 | 6 | 3 | 27 | 6 | 25 |
| 14 | 6 | 3 | 29 | 14 | 28 |
| 15 | 7 | 1 | 없음 | 0 | 4 |
| 16 | 7 | 1 | 없음 | 16 | 5 |
| 17 | 8 | 1 | 없음 | 8 | 7 |
| 18 | 8 | 1 | 없음 | 18 | 8 |
| 19 | 9 | 1 | 없음 | 4 | 11 |
| 20 | 9 | 1 | 없음 | 20 | 12 |
| 21 | 10 | 1 | 없음 | 10 | 14 |
| 22 | 10 | 1 | 없음 | 22 | 15 |
| 23 | 11 | 1 | 없음 | 2 | 19 |
| 24 | 11 | 1 | 없음 | 24 | 20 |
| 25 | 12 | 1 | 없음 | 12 | 22 |
| 26 | 12 | 1 | 없음 | 26 | 23 |
| 27 | 13 | 1 | 없음 | 6 | 26 |
| 28 | 13 | 1 | 없음 | 28 | 27 |
| 29 | 14 | 1 | 없음 | 14 | 29 |
앞 30개 정점만 보여 드립니다.
사용 방법
- 1부모 배열을 넣습니다. "-1 0 0 1 1 2"는 0이 뿌리이고 1·2가 그 자식이라는 뜻입니다.
- 2예제에서 한 줄 트리·별 모양·무작위 트리를 골라 볼 수도 있습니다.
- 3각 정점의 서브트리 크기와 무거운 자식, 그리고 만들어진 체인 목록이 나옵니다.
- 4두 정점을 고르면 그 경로가 어느 체인 조각으로 나뉘는지 표로 나옵니다.
- 5가벼운 간선 수와 조각 수를 log₂n과 견주어 O(log n)인 것을 확인합니다.
자주 묻는 질문
각 정점에서 서브트리가 가장 큰 자식으로 가는 간선 하나만 «무겁다»고 부르고 나머지는 모두 «가볍다»고 부릅니다. 정점마다 무거운 간선이 많아야 하나이므로 무거운 간선들을 이어 붙이면 갈래가 지지 않는 곧은 줄, 곧 체인이 됩니다.
가벼운 간선을 탈 때마다 서브트리 크기가 반 이하로 줄기 때문입니다. 정점 v의 자식 c로 가는 간선이 가볍다면 c는 가장 큰 자식이 아니므로 size(c) ≤ size(v)/2입니다. 크기가 n에서 1까지 반씩 주는 데 log₂n번이면 되니 가벼운 간선은 그만큼뿐이고, 체인이 바뀌는 것은 가벼운 간선을 탈 때뿐이라 조각 수도 그만큼입니다.
아닙니다. HLD는 «경로를 배열의 연속 구간 몇 개로 바꿔 주는» 일만 합니다. 그 구간의 합이나 최댓값을 실제로 구하려면 세그먼트 트리나 펜윅 트리를 얹어야 하고, 조각이 O(log n)개에 각 조각이 O(log n)이라 전체가 O(log² n)이 됩니다. LCA는 HLD가 덤으로 줍니다.
균형 잡힌 트리에서 많아집니다. 한 줄로 늘어선 트리는 통째로 체인 하나라 어떤 경로도 조각이 하나이고, 별 모양이면 잎에서 잎으로 갈 때 셋입니다. 이진 균형 트리처럼 갈래가 고르게 지는 경우에 log n에 가까워지며, 이 계산기로 정점 수를 늘려 가며 재어 보실 수 있습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서만 이뤄지고, 입력값은 이 기기의 저장소에만 남습니다.
알아두면 좋은 점
- 정점 2000개까지 다룹니다. 설명을 위해 체인과 경로를 모두 펼쳐 들고 있기 때문입니다.
- 분해와 질의만 합니다. 체인 위에 얹는 세그먼트 트리는 다루지 않습니다.
- 간선에 값이 붙는 경우(edge query)는 정점에 값이 붙는 경우와 달리 LCA를 한 칸 건너뛰어야 합니다. 여기서는 정점 기준으로만 보여 줍니다.
- 무작위 트리 수십 개·질의 수천 개에서 경로를 완전탐색으로 구한 값과 대조했고, 가벼운 간선 수가 log₂n을 넘지 않는 것도 확인했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.