스파스 테이블(Sparse Table), Binary Lifting

여기, 여기, 여기를 보면 기본 개념에 대해서는 얼추 파악할 수 있다.

LCA를 구할때 쓰는 Binary Lifting도 sparse table의 일종이다.

기본 개념은 O(N)걸리는 쿼리를 전처리 작업을 통해서 O(log N)이나 O(1)로 줄인다고 하는것

그걸 위해서 A[N] 이란게 있다고 하면 ST[log2(N)][N] 이런 스케일로 테이블 정의하고..

ST[0][N] = A[N]으로 초기화 한다음에

REP1(i, max_level)REP(j,N) ST[i][j] = ST[i-1][어쩌구]..저쩌구 이런식으로 한다.

i가 1증가할때 마다 2배씩 뛰는건데 자세한건 위의 링크를 참조하자.

기본LCA문제를 풀 때에도 ancestor 만들때 위의 기술을 사용하고,

단순히 합성함수를 효율적으로 구하는 문제에서도 사용된다.

트리 정점 a, b의 경로에서 가장 가중치 큰거나 작은거 하나 출력하는 문제에서도 사용되고,

a,b경로중 k번째 정점을 찾는 문제에서도 사용된다.

아직 나도 통달한건 아니라 이정도로 기록해둔다.