ps:경로_쿼리
경로 쿼리
- 트리에서 u와 v를 잇는 경로상의 엣지들 (또는 노드들) 에 대한 뭔가를 물어보는 쿼리이다.
- 가장 간단한 것은 경로의 길이를 묻는 문제이다. 경로상의 엣지들에 대해서 sum 쿼리를 요구하는 것과 똑같다.
- 해결 방법을 정리하면 아래와 같다.
- 업데이트가 있을때: HLD
- (업데이트가 없어도 따로 생각하기 귀찮으면 그냥 이렇게 써도 된다)
- 업데이트가 없을때: 스파스 테이블:
- 업데이트가 없을때 + 쿼리 연산에 역연산이 존재:
- 업데이트가 없는 구간 최솟값 쿼리:
업데이트가 있을때: HLD + 구간쿼리
- 경로 쿼리를 해결하는 가장 단순한 방법은, 그냥 무지성으로 HLD를 적용하는 것이다. 그냥 이걸로도 웬만하면 대충 다 통한다.
- O(n)의 전처리를 거치면 임의의 두 점이 들어왔을때 O(logn)시간을 써서, O(logn)개의 구간으로 변환할수 있다.
- 각각의 구간들에 대해서 구간 쿼리에서 쓰던 테크닉들을 그냥 적용하면 된다. 한개의 구간을 처리하는데에 걸리는 시간에 구간의 갯수O(logn)을 곱하면 쿼리를 처리하는 시간복잡도가 나온다.
- 예를 들면
- (업데이트가 없는) 경로 합 쿼리 ⇒ 누적합을 이용하면 한개 구간을 O(1)에 처리가능. 따라서 쿼리당 O(logn)
- (업데이트가 없는) 경로 최솟값 쿼리 ⇒ 스파스 테이블을 이용하면 한개 구간을 O(1)에 처리가능. 따라서 쿼리당 O(logn)
- (업데이트가 있는) 경로 합 쿼리 ⇒ 세그먼트 트리를 이용하면 한개 구간을 O(logn)에 처리가능. 따라서 쿼리당 O(log^2n)
- 포인트 업데이트는 한개의 구간에만 적용되므로 그냥 O(logn)
- (업데이트가 있는) 경로 최솟값 쿼리 ⇒ 세그먼트 트리를 이용하면 한개 구간을 O(logn)에 처리가능. 따라서 쿼리당 O(log^2n)
- 포인트 업데이트는 구간에만 적용되므로 그냥 O(logn)
업데이트가 없을때: binary lifting
- 업데이트가 없는 쿼리에 대해서는, 스파스 테이블을 쓸수 있다.
- u↔v 의 경로를, u↔lca(u,v) 와 lca(u,v)↔v로 나눠서 각각을 계산한다음에 합치는 것이다. 이렇게 나누면 각각의 경로는 k번째 부모노드 까지의 경로이다.
- 스파스 테이블로 2^i번째 부모노드까지의 경로에 대한 값을 계산해두면, O(logn)에 각각을 계산할수 있다.
- 이렇게 스파스테이블을 만들면, 이것으로 lca도 자연스럽게 같이 구할수 있다.
- 그래서, 전처리에 O(nlogn), 쿼리 하나당 O(logn)에 처리가 가능하다.
경로의 길이
- 경로의 길이는 결국 경로 합 쿼리와 동일하다.
- 루트에서부터 각 노드까지의 경로의 합을 모두 저장해둔다. 누적합과 비슷한 형태가 된다. O(n)이 걸린다.
- weight가 없는 트리라면, 그냥 depth가 된다.
- LCA를 이용해서 u↔v 의 경로를 u↔lca(u,v) 와 lca(u,v)↔v로 나누면, u↔lca(u,v)의 길이는 dist[u] - dist[lca] 가 된다. lca(u,v)↔v도 마찬가지.
- 결국 LCA만 구하면 나머지는 O(1)에 계산 가능.
- 전처리 O(n), 쿼리 O(logn)으로 LCA를 계산한다 치면, 총 시간 복잡도도 전처리 O(n), 쿼리 O(logn)이 된다.
- 합 쿼리 뿐만 아니라 역연산이 있는 쿼리에 모두 적용 가능하다.
경로 최솟값 쿼리
- 일반적인 방법을 먼저 정리하자. 역연산이 없으니까 경로 합 쿼리처럼 처리할수는 없다.
- binary lifting 방법으로 처리하면, 전처리에 O(nlogn), 쿼리 하나당 O(logn).
- HLD와 세그트리를 사용하면, 전처리에 O(n), 쿼리 하나당 O(log^2n)
- HLD와 스파스테이블을 사용하면, 전처리에 O(nlogn), 쿼리 하나당 O(logn)
- 이제 경로 최솟값 쿼리에 적용되는 특수한 방법을 보자
- 원래는 트리가 미리 주어져있는 상황보다는 트리를 만들어나가면서 처리해야 하는 문제에서 쓰는 해법인데.. 트리가 미리 주어져있는 상황이어도 못쓸 이유는 없다.
- 기본 컨셉은 엣지들을 정렬한 다음에, 가중치가 큰 엣지부터 하나씩 추가해나가다가, u와 v가 연결되는 순간을 찾으면, 그때 추가한 엣지의 가중치가 u-v경로상의 최솟값 엣지가 된다.
- 이것은 Disjoint set을 이용해서 처리한다.
- 그런데, 쿼리들..즉 (u,v)페어가 한개가 아닌데, 매번 엣지를 추가할때마다 모든 페어에 대해서 연결여부를 확인하고 있을수가 없잖아?
- 이것을 효율적으로 하는 방법들이 존재한다.
- 일단 이런 식의 형태의 작업을 무지성으로 처리하는 테크닉이 병렬 이분 탐색 (Parallel Binary Search; PBS)이다. PBS를 적용해서 풀면 O(logn*(n+Q)*α(n)) 가 걸린다.
- 경로의 최솟값이 LCA가 되도록 트리를 재구성하는 방법. O(n*α(n) + Qlogn) 또는 O(n*α(V) + Q + nlogn)
- 오프라인 쿼리 테크닉 + smaller to larger 테크닉. O(n*α(n) + QlogQ)
- 사실 얼핏 찾아보면 이 외에도 더 많은 방법들이 있는거 같다
- 이론적으로는 더 효율적인것 같긴 한데.. 실용적으로 쓰기는 어렵지 않을까 추측 (자세히 찾아보진 않아서 근거는 없다)
- 구간 최솟값 쿼리에서도 Farach-Colton 방법이나, 4-Russian 방법 등등으로 이론적으로 O(n)전처리 O(1)쿼리가 가능은 하지만 PS에서 안쓰이는 것과 비슷한 느낌?
LCA를 이용한 방법
- 원래 트리의 엣지들을 추가하면서 새로운 형태의 트리를 만든다.
- 현재 추가된 엣지의 가중치가, 새 트리에서는 노드에 매핑되어 저장된다. 그리고 그 노드가 지금 합쳐진 컴포넌트들의 LCA가 되도록 트리를 만드는 것이다.
- 엣지가 추가되면서 노드들이 연결되어서 컴포넌트들로 뭉쳐질것이다. 이 컴포넌트들은 각각의 트리로 표현될텐데, 그때의 루트 노드를 따로 저장해놓는다. 이제 (u,v)엣지를 추가한다면, 새 트리에서는 u와 v에 엣지를 연결하는 것이 아니라, u가 속한 컴포넌트의 루트노드와 v가 속한 컴포넌트의 루트노드를 연결해주게 된다. 이것도 그대로 연결하는 것이 아니라.. 새로운 노드 p를 하나 추가해서 그 노드가 u의 루트노드와 v의 루트노드의 공통 부모가 되게 한다. 이러면 p는 합쳐진 컴포넌트의 루트노드가 된다. 그리고 p에 현재 추가된 엣지의 가중치를 매핑시켜 저장한다
- 이렇게 트리를 다 만들고 나면, u와 v가 연결된 시점의 가중치는 u와 v의 LCA노드에 매핑된 값이 된다.
- 결국 원래 트리에서의 경로 최솟값 쿼리를, 새 트리에서의 LCA 쿼리로 처리할수 있다.
- n개의 엣지를 dsu로 추가하면서 새 트리를 만드는데에는 O(n*α(n))이 걸린다.
- 트리에서 LCA 쿼리를 처리하는 것은 HLD를 사용했을때 전처리 O(n), Q개 쿼리를 처리하는 것에 O(Qlogn)가 걸린다. RMQ로 변환해서 Sparse table을 써서 한다면, 구축에 O(nlogn), Q개쿼리 처리에 O(Q)가 된다.
- 보통 Q와 n이 비슷하면 전자의 방법이 더 빠르다
- 암튼 총 시간 복잡도는 O(n*α(n) + Qlogn) 또는 O(n*α(V) + Q + nlogn) 이다
오프라인 쿼리
- 각 컴포넌트마다, 이 컴포넌트의 원소를 포함하는 쿼리의 번호들을 갖고 있는 집합을 만들어준다.
- 한 쿼리는 두개의 노드를 포함하므로, 동일한 번호를 갖는 컴포넌트는 두개이다
- 컴포넌트가 합쳐질때마다, 두 컴포넌트의 쿼리번호집합을 합치게 된다.
- 합치는 과정에서 동일한 쿼리번호가 양쪽 집합에 있었다면, 현재 추가된 엣지의 가중치가 그 쿼리의 해답이 된다.
- 두개의 쿼리번호 집합을 합치는 것을 small-to-large 방식으로 처리하면, 모든 쿼리번호집합이 합쳐질때까지 O(QlogQ)번의 연산으로 해결되게 된다.
- 총 시간복잡도는 O(E*α(V) + QlogQ)이다
ps/경로_쿼리.txt · 마지막으로 수정됨: 2023/01/06 02:41 저자 teferi
토론