Tree에서 두 nodes u와 v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다.

그렇다면 어떻게 LCA를 구할 수 있을까?

Method 1

Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다.

1. root에서 u, v까지의 경로를 각각 배열에 저장한다
2. 두 배열을 비교하여 얻은 공통 조상 중, root에서 가장 멀리 떨어진 것이 LCA이다.

시간 복잡도는 O(N)이다.

Method 2

또 다른 Naive 한 풀이는, Parent Pointer를 이용하는 것이다. method 1과 다르게, u 또는 v에서 시작해 root 방향으로 순회를 한다.

1. 먼저, u에서 root로 순회하면서 ancestors를 저장한다.
2. v에서 root로 순회할 때, u에서의 ancestors와 동일한 것이 있는지 확인한다. 이때, 가장 먼저 동일한 것이 곧 LCA이다.

시간 복잡도는 O(N) 이다.

Method 3

	   1
     /   \
    2     3
  /   \
 4     5

위와 같은 tree가 있을 때, DFS를 이용한 Euler tour를 한다고 해보자. sub-tree의 root인 r에 도달 했을 때, r의 자손인 u로 갔다가, 다시 r로 돌아와 다른 자손 v로 내려가게 된다. 즉, u와 v는 공통 조상인 r을 반드시 거치게 되는데, 이 특징을 이용해서 문제를 풀 수 있다.

먼저, 세 가지 배열이 필요하다.

• dfs_node[]: Euler tour로 방문하는 nodes를 순서대로 저장
• dfs_level[]: Euler tour로 방문하는 nodes의 level을 순서대로 저장
• firstOccur[]: 각 node가 Euler tour에서 처음으로 나타난 index

위 상황에서는, 다음과 같이 배열을 생성한다.

dfs_node[]   = {1, 2, 4, 2, 5, 2, 1, 3, 1}
dfs_level[]  = {0, 1, 2, 1, 2, 1, 0, 1, 0}
firstOccur[] = {0, 1, 7, 2, 4 }

이를 이용해서 LCA(4, 3)을 구해보자. 각 node 가 처음 발생한 index는 7, 2다. 공통 조상은 2와 7 사이에 level이 가장 낮은 node일 것이다. 이에 따라 dfs_level[2:7]를 조사하면, index = 6 일 때, level = 0으로 최소인 이 node가 곧 lca가 되며, dfs_node[6]를 통해 node 1인 것을 확인할 수 있다.

이때, 구간의 최소를 하나하나 비교하여 찾는 것이 아니라, Segment Tree를 기반으로 한 Range Minimum Query(RMQ)로 찾으면 더 빠를 것이다.

시간복잡도는, DFS를 통해 배열을 생성하고 Segment Tree를 생성하는데 O(N)이고, 매 Query마다 O(logN)이다.

Method 4

method 2에서는 root 방향으로 순회하며 서로의 ancestors를 비교한다. 그러나, 모든 ancestors를 하나하나 비교하기 때문에 빠르지 않다. 대신에, Binary Search에서 찾으려는 값이 mid보다 작으면 (l, mid-1)를 조사하고, mid보다 크면 (mid+1, r)을 조사하는 것처럼, ancestor의 조사 구간을 선택하면서 풀면 더 빠를 것이다.
먼저, 다음과 같이 각 node의 2^k 번째 조상을 미리 저장한다.

memo[i][j] = i-th node의 (2^j)-th ancestor
		   = memo[ memo[i][j-1] ][j-1]

( 0 <= j <= log ), ( log = ceil( log2(N) ) )

이를 이용하여 Binary 하게 LCA를 찾는다.

1. u 와 v의 level을 동일하게 맞춘다. 이때, u == v 라면, 다른 하나가 조상인 것이다.
2. loop j: log to 0
	if ( memo[u][j] != memo[v][j] ){
    	u = memo[u][j];
        v = memo[v][j];
    }
3. memo[u][0] 이 LCA이다. (memo[v][0])

이렇게 Dynamic Programming을 이용해서 Binary하게 LCA를 찾을 수 있는데, 이를 Binary Lifting 방법이라고 부른다.

시간 복잡도는, dp 생성에 O(NlogN)이고, 매 Query마다 O(logN)이다.
(이러한 형식의 rmq용 data structure를 sparse table 이라고도 부른다.)