#6 Sparse_table, LCA, Offline_query

Sparse table이란 행렬 중에서 행렬의 값의 대부분이 0인 경우를 나타내는 행렬

 

우리가 그래프를 표현하는 방식 중에 인접 행렬 방식을 활용할 때에 있어서 특수한 경우에는. 그래프의 모든 정보를

표현할 필요 없을 때가 있다. 

예시 문제

백준 17435 (합성함수와 쿼리) c++

 

LCA는 트리에서 사용되는 개념이다.(최소공통조상)

트리에 존재하는 어떤 두 정점에 대해서, 각각의 부모를 타고 루트까지 올라갔을때 처음으로 동시에 만나게 되는

정점을 의미

LCA(5, 8) = 1 

1에서 둘이 동시에 만나게 됩니다.

 

LCA를 naive하게 구현하는 방법은 루트노드까지 부모를 타고 올라가면서 최초로 겹치는 노드를 찾는 방법이고

시간복잡도는 O(n)이다.

 

Sparse Table을 활용하는 가장 대표적인 알고리즘은 LCA로 O(log n)의 시간복잡도를 지닌다.

가장 쉽게 구현 가능하고 여러가지 응용이 가능한 방법이라는 장점을 가지고 있다.

 

물론 LCA는 Sparse Table을 이용하는 방식이 아니더라도 여러가지 방식으로 구할 수 있다. 

대표적으로 ett와 segment tree를 이용하거나 hld를 이용하는 방식이 있다

예시 문제

백준 11438번 (LCA 2) C++

 

단순 LCA를 구하는 문제 말고도 두 트리의 경로에 대한 여러 문제들도 LCA를 활용해서 해결할 수 있다.

 

트리의 두 정점 사이의 경로는 유일하다. 두 정점 a, b사이의 경로는 a-lca(a, b)-b 사이의 경로로 축약 가능하다.

따라서 sparse table을 활용한다면 a와 b사이의 경로에 관한 여러 문제를 해결할 수 있다.

예시 문제

백준 1761번 (정점들의 거리) c++

 

Offline Query

쿼리 문제를 만났을 때, 출력을 해야하는 쿼리마다 그때그때 정답을 출력해야할까?

 

그때 그때 마다 정답을 출력해야 할 때는 온라인 쿼리라고 하고, 꼭 그럴 필요가 없이 쿼리의 

순서를 적절히 우리가 원하는 순서로 바꿔서 문제를 해결하는 방식을 오프라인 쿼리라고 한다.