Sparse Table을 이용한 LCA의 VlgV 시간 해법

LCA는 Tree의 기초 문서에 설명되어있다.

임의의 트리의 정점의 갯수를 V라고 했을 때 LCA를 O(VlgV) 시간에 구하는 방법을 설명하고자 한다.

각 노드와 모든 n마다 그 노드의 2^n번째 부모를 저장해놓는다. n은 lgV까지만 저장하면 되므로 저장공간은 O(VlgV)만큼 필요하다.

이러한 표 또한 O(VlgV)만에 채울 수 있는데, 왜냐하면 (어떤 노드의 2^n번째 부모) == (2^(n-1)번째 부모의 2^(n-1)번째 부모)이기 때문이다.

이제, 두 노드의 LCA를 구해보자.

두 노드를 a, b라고 하고, 노드 x의 깊이를 h(x)라고 하자.

라고 하자.

b의 (h(b)-h(a))번째 부모를 b' 라고 하자. 이는 O(lgV) 시간에 구할 수 있다.

a와 b의 LCA는 a와 b'의 LCA이다.

두 노드의 깊이가 같으므로, lca(a,b')=x 라고 했을 때, a의 (h(a)-h(x))번째 부모는 b'의 (h(b')-h(x))번째 부모와 같고, 그 윗쪽 부모는 당연하게 같다.

따라서, a의 i번째 부모와 b'의 i번째 부모가 다르도록 하는 가장 큰 i를 잡으면, a의 i+1번째 부모가 a와 b의 LCA가 됨을 알 수 있다.

이러한 i를 찾으려면,

이러한 그림을 보면 이진 탐색을 하면 됨을 알 수 있다.

이진탐색과 원리는 같으나 구현이 더 간단한 솔루션은,

j를 (log_2)i 부터 0까지 돌리면서,

a와 b의 2^j번째 조상이 다르면 a와 b를 각각의 2^j번째 조상으로 바꿔준다.

마지막에 a와 b가 다르면 a와 b를 각각의 부모로 바꿔준다.

LCA는 a. 좀만 생각해보면 알 수 있다.