ps:lca
목차
최소 공통 조상 (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)이다
관련 문제
ps/lca.txt · 마지막으로 수정됨: 2024/01/10 09:16 저자 teferi
토론