Lowest-Common-Ancestor

트리 구조에서 여러 노드의 공통 조상을 찾는 알고리즘인 LCA에 대해서 알아보겠습니다.

LCA

두 노드의 루트로부터의 깊이를 확인합니다.
두 노드를 같은 깊이가 되도록 맞추어줍니다.
이는 더 깊은 노드에서 조상을 거슬러 올라가면 됩니다.
같은 깊이가 되었다면 공통 조상을 찾을 때까지 함께 거슬러 올라가도록 합니다.

몇가지 값을 미리 저장해두면 계산이 편리해집니다.
그래서 다음 두가지를 미리 계산하여 저장하도록 합니다.
각 노드마다 루트로부터의 깊이를 계산하여 저장합니다.
각 노드마다 거슬러 올라가는 조상목록을 순서대로 저장합니다.

깊이와 부모

void get_p(int i) {
    for(int j : v[i]) {
        if(!d[j]) {
            d[j] = d[i] + 1;
            p[j].push_back(i);
            mxd = max(mxd, d[j]);
            get_p(j);
        }
    }
}

이런 방식으로 계산하면 $O(d)$의 시간복잡도를 갖게 됩니다.
여기서의 d값은 최대 깊이를 의미합니다.
많은 문제에서는 이보다 더 빠른 속도를 요구합니다.
이제 더 효율적이고 빠른 방법을 알아보도록 하겠습니다.

Sparse-Table

sparse table을 이용하면, 조상목록을 거슬러가는 속도를 개선할 수 있습니다.
기본적으로 위에서 보았던 알고리즘에서는 하나씩 올라가는 방식을 선택했기 때문에 $O(d)$의 시간복잡도를 가졌습니다.
sparse table을 적용하면 2의 거듭제곱만큼 한번에 올라갈 수 있습니다.
따라서, $O(log{d})$의 개선된 시간복잡도를 갖습니다.

이제 sparse table을 만드는 방법을 알아보겠습니다.

d[0] = 1;
p[0].push_back(0);
get_p(0);
for(int j = 0; 1 << j < mxd; j++) {
    for(int i = 0; i < N; i++) {
        int k = p[i][j];
        p[i].push_back(p[k][j]);
    }
}

p[i][j]는 i번째 노드의 $2^{j}$위 조상을 가르킵니다.
해당 반복문에서는 i번째 노드의 $2^{j+1}$위 조상은 i번째 노드의 $2^{j}$위 조상의 $2^{j}$위 조상이라는 것을 통해 테이블을 채워갑니다.

완성된 sparse table을 이용하여 더 빠르게 LCA를 알아낼 수 있습니다.

if(d[A] < d[B]) swap(A, B);
for(int j = 0, diff = d[A] - d[B]; diff; j++, diff >>= 1) {
    if(diff & 1) A = p[A][j];
}
if(A != B) {
    for(int j = p[0].size()-1; j >= 0; j--) {
        if(p[A][j] != p[B][j]) {
            A = p[A][j];
            B = p[B][j];
        }
    }
    A = p[A][0];
}
// LCA = A

Heavy-Light-Decomposition

흔히 HLD라고 불리는 알고리즘입니다.
아직 공부를 하지 못한 부분이기 때문에 나중에 더 공부하여 내용을 채우겠습니다 :: TBD