희소 배열 (Sparse Table)

트리가 존재할 때, 해당 노드의 N번째 앞에 있는 조상노드를 빠르게 찾기 위해 사용하는 알고리즘이다.

(그래프에서도 사용할 수 있기는 하는 것 같다.)

기본 아이디어는 2의 N제곱으로 조상 노드를 log만큼 이동하는 것이다.

그래서 O(logN) 만에 N번째 조상 노드를 찾아갈 수 있다.

여기서 N이 0일때는 부모 노드를 가리킨다.

 

보통 2차원 배열로 표현을 한다.

parent [logn+1][n+1] 크기로 만든다.

각 노드들의 부모 노드들은 0번 이동한 것이니 parent[0][i] 노드에 부모 노드들을 넣어준다.

i번 노드의 2^0번째 부모노드니 바로 위의 부모 노드가 될 것이다.

 

for i in range(1, logn+1): # 2^i번 부모 노드

    for j in range(1, n+1): # j번째 노드

        parent[i][j] = parent[i-1][parent[i-1][j]]

이렇게 하면 각 노드들의 희소 배열들이 세팅이 된다.

j번의 4번째 부모 노드는 j번의 2번째 부모노드의 2번째 부모노드가 되는 것이니

저 식을 이렇게 해석하면 된다.