최소 공통 조상 (Lowest Common Ancestor / LCA)

LCA를 구하는 알고리즘이라고 하지만, 그냥 노드 한쌍에 대해서만 LCA를 구하는 것은 어떻게 하든 O(n)에 처리된다.
여기서 다루려는 알고리즘은, q개의 노드 쌍에 대해서 LCA를 구하는 것, 즉 LCA 쿼리들을 빠르게 처리하는 방법이다.
세줄 요약을 먼저 하면
- 바이너리 리프팅과 HLD, 여기에 추가로 RMQ sparse table 방법 정도만 알아두면 충분하다.
- 그냥 LCA만 구하려면
  - 이론상으로는 Farach-Colton and Bender Algorithm이 최적이나 실용적으로는 별로이므로 쓰지 말자
  - 일반적으로는 HLD를 사용해서 구하자.
    - 이 용도의 HLD는 일반 HLD보다 좀더 적은 작업량으로도 가능하다
  - n에 비해 쿼리 갯수가 매우 크면, RMQ로 변환 후에 sparse table을 사용하자
- LCA뿐만 아니라 경로 쿼리를 처리해야 한다면
  - 업데이트 없는 쿼리라면, 바이너리 리프팅으로 LCA와 경로쿼리를 해결한다
  - 업데이트 있는 쿼리라면, HLD로 LCA와 경로쿼리를 해결한다

LCA 알고리즘

LCA를 구하는데 사용가능한 알고리즘들은 매우 다양하다.
크게 트리상에서 리프팅 하는 알고리즘들과 RMQ문제로 변환해서 푸는 알고리즘으로 나눠보겠다
트리에서 리프팅하는 알고리즘
- 기본적으로는 각 노드들로부터 부모노드 쪽으로 거슬러 올라가다가 일치하는 노드를 만나면 그곳을 LCA로 체크하는 방법이다.
- 이때 부모노드를 향해 한칸씩 올라가는것보다 효율적으로 하기 위해서, 바이너리 리프팅이나 HLD를 이용한다
- 바이너리 리프팅 (또는 바이너리 점핑이라고도 불린다) 알고리즘
  - sparse table에 각 노드의 2^k번째 조상노드를 저장해두어서, 그것을 통해서 2^k 조상으로 점프하는 방법이다.
  - 더 깊은 쪽에 있는 노드에서 먼저 리프팅해서 뎁스를 동일하게 맞춘다음. 이제 같은 노드에서 만날때까지 두 노드에서 동시에 리프팅해간다.
  - 전처리에 O(nlogn), 쿼리 하나당 O(logn)이 걸린다
- HLD
  - 트리를 체인들로 나눠서, 체인의 탑 노드로 점프하는 방법이다. 두 노드가 같은 체인에 걸릴때까지 반복하면 된다.
  - 전처리에 O(n), 쿼리 하나당 O(logn)이 걸린다
RMQ문제로 변환해서 푸는 알고리즘
- 트리에서 오일러 투어 경로를 찾으면 1차원 시퀀스가 되고, 여기에서 RMQ(구간 최솟값 쿼리)를 돌리면 그것이 LCA가 된다.
- 1차원 시퀀스로 변환하는 것은 DFS를 이용해서 O(n)에 처리된다. 이제 1차원 시퀀스에서 구간 최솟값 쿼리를 구하는 문제로 바뀐다.
- 기본적인 구간 최솟값 쿼리를 처리하는 방법을 응용하면
  - 세그먼트 트리를 사용해서 RMQ를 처리하면, 전처리에 O(n), 쿼리당 O(logn)이 걸린다
  - sparse table을 사용해서 RMQ를 처리하면, 전처리에 O(nlogn),쿼리당 O(1)이 걸린다
  - 만약 오프라인 쿼리라면, arpa 트릭을 사용해서 q개의 쿼리를 O(n*α(n)+q)에 처리할수 있다
- 여기에 오일러 투어 경로로 만들어진 시퀀스만의 특성인 '인접한 두개의 수는 차가 1이다'라는 점을 활용하면 어찌어찌 구간을 쪼개서 여러개의 sparse table로 만들어서 전처리 O(n), 쿼리당 O(1)에 처리하는것도 가능하다고 한다
  - Farach-Colton and Bender Algorithm 참고
- 그리고 역으로 일반적인 RMQ 문제를 LCA문제로 변환하는 것은, 처음 배열에서 cartesian tree를 만들면 된다고 한다. 이렇게 하면 일반적인 RMQ문제에 Farach-Colton and Bender Algorithm를 적용할 수 있어서 RMQ도 전처리 O(n), 쿼리당 O(1)에 처리가 가능해진다고 한다
- 이 외에, 오프라인 쿼리라면 Tarjan's offline algorithm으로 q개의 쿼리를 O(n+q)에 처리 가능하다고 하다. 오프라인 RMQ를 arpa 트릭으로 처리하는 방법을, 오일러투어 경로를 돌면서 적용한 방법이라고 생각하면 된다. 물론 원조는 이 알고리즘이고, arpa 트릭이 나중에 나온것이지만..

그래서 뭘 써야 하는가 - LCA만 구할때

LCA값만 구하면 되는 문제들이 있다. 진짜로 LCA를 찾는 것이 목적인 문제도 당연히 있고, 아니면 두 노드가 조상-자손 관계에 있는지 확인하기 위한 문제라든가..
우선 대부분 문제에서 q가 n보다 큰 문제는 별로 안나오는 듯. q랑 n이 비슷하거나 q가 n보다 작거나..
본래 HLD는 체인들을 구한다음 체인들이 구간내에 연속되도록 구간을 재배열하는 것까지가 포함되지만, LCA만 구하는 용도로 쓴다면 그냥 체인들만 구해도 된다.
q랑 n이 10만정도인 문제 (LCA 2)에서 돌렸을때..
- tarjan offline 1024ms
- RMQ+스파스테이블 820ms
- RMQ+segtree 1308ms
- HLD 740ms
Farach-Colton and Bender Algorithm 이 이론적으로는 가장 빠른 시간복잡도를 갖지만, 실제로는 느리다는 평이 있다. (직접 구현은 안해봤다)
마찬가지로 Tarjan's offline algorithm도 시간복잡도상 제일 빠르지만, 실제로 구현해봤을때는 다른 알고리즘보다 느렸다
HLD와 RMQ+segtree가 둘다 O(n + qlogn)이지만 HLD가 훨씬 빠름
HLD가 O(nlogn + q)인 RMQ+스파스테이블보다도 빠름.
결국 LCA만 구해야 할 경우에 경쟁력있는것는 HLD와 RMQ 스파스테이블 두가지인듯. 그 이상은 굳이 안해봐도 될듯
- 일반적으로는 HLD가 가장 빠르다. 이걸 쓰자.
- q가 n보다 많이 크다면 쿼리시간이 더 빠른 RMQ 스파스테이블을 써보자. 메모리 사용량도 스파스테이블이 절반정도만 먹는다

그래서 뭘 써야 하는가 - LCA + 경로 쿼리

경로 쿼리 참조.
LCA를 필요로 하는 문제들 중 많은 수는 경로 쿼리를 처리하기 위함이다. 두 노드 u,v 간의 경로 u→v 에 대한 쿼리를 처리할때, 경로를 u → lca, lca → v 로 나누어 각각에 대한 쿼리를 처리한 뒤 합치는 방식으로 사용된다.
그러면 이제 lca를 구한 다음에, u→lca 까지의 경로와, lca→v 까지의 경로에 대해서 뭔가를 계산해줘야 하는 경우들이 많은데. 이게 역연산이 가능한 경우라면 (대표적으로는 구간들의 합으로 계산되는 거리 구하기 문제), f(u,lca) = f(root,u)- f(root,lca) 와 같은식으로 누적합 비슷한 방법으로 처리가 가능하지만, 복잡한 쿼리들은 경로를 구간들로 쪼개서 뭔가를 해줘야 한다.
- 펜윅트리로 처리 가능한 연산과, 세그먼트 트리를 써야 하는 연산이라고 생각하면 간단하다.
그래서 LCA를 구할때도, LCA 자체를 빨리 구하는 것을 넘어서, LCA를 구하고 이러한 구간처리까지 함께 효율적으로 해줄수 있는 방법을 사용하는 것이 좋다.
- RMQ로 변환해서 LCA를 구하는 방법은, 이 목적에는 도움이 되지 않는다.
두 노드에서 리프팅해서 LCA까지 찾아가는 방법들은, 그렇게 올라간 과정이 경로로 남게 되므로 이 목적에 적합하다.
- 업데이트가 없는 경로 쿼리를 처리해야 한다면, 바이너리 점핑 테이블을 쓰면 된다. 전처리 O(nlogn), LCA쿼리 O(logn), 경로쿼리 O(logn)이다. 바이너리 점핑 테이블을 만들어두면 k번째 조상 찾기와 같은 쿼리도 O(logn)에 처리할수 있다
- 업데이트가 있는 경로 쿼리라면, HLD가 필요하다. HLD로 쪼갠 구간들을 segment tree 로 관리한다 치면 경로 쿼리에 O(log^2n)이 걸린다. 전처리는 O(n), LCA쿼리는 O(logn), 경로쿼리 O(log^2n)이다

목차

최소 공통 조상 (Lowest Common Ancestor / LCA)

LCA 알고리즘

그래서 뭘 써야 하는가 - LCA만 구할때

그래서 뭘 써야 하는가 - LCA + 경로 쿼리

관련 문제