====== 최소 공통 조상 (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뿐만 아니라 [[ps:경로 쿼리]]를 처리해야 한다면 * 업데이트 없는 쿼리라면, 바이너리 리프팅으로 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만정도인 문제 ([[ps:problems:boj:11438]])에서 돌렸을때.. * 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 + 경로 쿼리 ==== * [[ps:경로 쿼리]] 참조. * 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:problems:boj:11437]]: n<50,000, q<10,000 * [[ps:problems:boj:11438]]: n<100,000, q<100,000