ps:lca
목차
최소 공통 조상 (Lowest Common Ancestor / LCA)
- 그냥 노드 한쌍에 대해서만 한번 LCA를 구하는 것은 O(n)에 처리된다. 이것은 별 문제가 아니다.
- 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가 된다.
- 오일러투어 시퀀스를 찾는것은 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 트릭을 사용하는 것과 비슷한 원리일것 같다.
그래서 뭘 써야 하는가 - 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 - lca - v 로 찾아서 경로상에 대한 쿼리를 처리하는데 쓴다.
- 그러면 lca를 구한 다음에, u에서 lca까지의 경로와, v에서 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 · 마지막으로 수정됨: 2023/02/09 14:49 저자 teferi
토론