알고리즘 LCA 와 RMQ 문제

http://dongxicheng.org/structure/lca-rmq/
1、  개술
LCA (Least Common Ancestors), 즉 최근 공공 조상 은 뿌리 가 있 는 나무 에서 두 개의 결점 u 와 v 의 가장 가 까 운 공공 조상 을 찾 는 문 제 를 말한다.RMQ (Range Minimum / Maximum Query), 즉 구간 의 가장 값 조회 란 다음 과 같은 문 제 를 말한다. 길이 가 n 인 수열 A 에 대해 몇 가지 질문 에 RMQ (A, i, j) (i, j < = n) 를 대답 하고 수열 A 에서 i, j 사이 의 최소 / 큰 값 을 되 돌려 준다.이 두 가지 문 제 는 실제 응용 에서 자주 발생 하 는 문제 로 본 고 는 현재 이 두 가지 문 제 를 해결 하 는 비교적 효율 적 인 알고리즘 을 소개 했다.
2、  RMQ 알고리즘
이 문제 에 대해 가장 생각 하기 쉬 운 해결 방안 은 옮 겨 다 니 는 것 이 고 복잡 도 는 O (n) 이다.그러나 데이터 양 이 매우 많 고 조회 가 빈번 할 때 이 알고리즘 은 문제 가 있 을 수 있 습 니 다.
이 절 은 비교적 효율 적 인 온라인 알고리즘 (ST 알고리즘) 으로 이 문 제 를 해결 하 는 것 을 소개 했다.온라인 알고리즘 이란 사용자 가 검색 어 를 입력 할 때마다 바로 검색 어 를 처리 하 는 것 을 말한다.이 알고리즘 은 일반적으로 비교적 긴 시간 으로 예비 처 리 를 하고 정보 가 충분 한 후에 비교적 적은 시간 으로 모든 조회 에 대답 할 수 있다.ST (Sparse Table) 알고리즘 은 RMQ 문 제 를 온라인 으로 처리 하 는 매우 유명한 알고리즘 으로 O (nlogn) 시간 내 에 예비 처 리 를 한 다음 O (1) 시간 내 에 모든 조회 에 대답 할 수 있다.
우선 사전 처 리 를 하고 동적 계획 (DP) 으로 해결한다.A [i] 를 설정 하 는 것 은 구간 의 가장 값 을 요구 하 는 수열 입 니 다. F [i, j] 는 i 개수 부터 2 ^ j 개수 의 최대 치 를 표시 합 니 다.예 를 들 어 수열 3, 24, 5, 6, 8, 1, 29 7, F [1, 0 은 첫 번 째 숫자 부터 길 이 는 2 ^ 0 = 1 의 최대 치 를 나타 내 는데 사실은 3 이다.F [1, 2] = 5, F [1, 3] = 8, F [2, 0] = 2, F [2, 1] = 4.이렇게 해서 DP 의 상태, 초치 가 모두 있 고 나머지 는 상태 전이 방정식 이다.우 리 는 F [i, j] 를 평균 두 단락 으로 나 누 었 다.상례 로 설명 하면 i = 1, j = 3 일 때 3, 2, 4, 5 와 6, 8, 1, 2 이 두 단락 이다.F [i, j] 가 이 두 단락 의 최대 치 중 최대 치 입 니 다.그래서 우 리 는 동적 계획 방정식 F [i, j] = max (F [i, j - 1], F [i + 2 ^ (j - 1), j - 1) 를 얻 었 다.
그리고 조회.k = [log 2 (j - i + 1)] 를 취하 면 RMQ (A, i, j) = min {F [i, k], F [j - 2 ^ k + 1, k]} 이 있 습 니 다.예 를 들 어 구간 [2, 8] 의 최대 치 를 요구 하려 면 [2, 5] 와 [5, 8] 두 구간 으로 나 누 어야 한다. 이 두 구간 의 최대 치 는 우리 가 직접 f [2, 2] 와 f [5, 2] 로 얻 을 수 있 기 때문이다.
알고리즘 위조 코드:

//   
 
INIT_RMQ
 
//max[i][j]     j   2^i        ，     ，num       
 
for i : 1 to n
 
  max[0][i] = num[i]
 
for i : 1 to log(n)/log(2)
 
  for j : 1 to (n+1-2^i)
 
     max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
 
//  
 
RMQ(i, j)
 
k = log(j-i+1) / log(2)
 
return MAX(max[k][i], max[k][j-2^k+1])

물론 이 문 제 는 선분 트 리 (구간 트 리 라 고도 함) 로 해결 할 수 있 습 니 다. 알고리즘 복잡 도 는 O (N) ~ O (logN) 입 니 다. 구체 적 으로 이 글 을 읽 을 수 있 습 니 다.
3、  LCA 알고리즘
이 문제 에 대해 가장 생각 하기 쉬 운 알고리즘 은 노드 u 와 v 에서 뿌리 노드 로 거 슬러 올 라 가 u 와 v 에서 뿌리 노드 로 가 는 경로 P1, P2 를 얻 는 것 이다. 그 중에서 P1 과 P2 는 두 개의 단일 체인 표 로 볼 수 있다. 이것 은 흔히 볼 수 있 는 면접 문제 로 전환 된다. [두 개의 단일 체인 표 가 교차 하 는 지 판단 하고 만약 에 교차 하 는 첫 번 째 점 을 제시한다.]이 알고리즘 의 전체적인 복잡 도 는 O (n) (그 중에서 n 은 나무 노드 개수) 이다.
이 절 은 이 문 제 를 해결 하 는 비교적 효율 적 인 알고리즘 두 가 지 를 소개 했다. 그 중 하 나 는 온라인 알고리즘 (DFS + ST) 이 고 다른 하 나 는 오프라인 알고리즘 (Tarjan 알고리즘) 이다.
온라인 알고리즘 DFS + ST 설명 (사상 은 나 무 를 무 방향 그림 으로 보고 u 와 v 의 공공 조상 은 반드시 u 와 v 사이 의 가장 짧 은 경로 에 있 습 니 다):
(1) DFS: 트 리 T 의 뿌리 부터 깊이 우선 옮 겨 다 니 기 (트 리 T 를 무 방향 그림 으로 보기) 하고 매번 도착 하 는 정점 을 기록 합 니 다.첫 번 째 결점 은 루트 (T) 로 한 변 을 지나 갈 때마다 단점 을 기록한다.각 변 이 마침 두 번 지나 가기 때문에 모두 2n - 1 개의 결점 을 기록 하고 E [1,..., 2n - 1] 로 표시 한다.
(2) R 계산: E 배열 의 첫 번 째 값 이 i 인 요 소 를 R [u] < R [v] 로 표시 할 때 DFS 가 방문 하 는 순 서 는 E [R [u], R [u] + 1,..., R [v] 이다.u 의 후손 을 포함 하고 있 지만 깊이 가 가장 작은 것 은 u 와 v 의 공공 조상 이다.
(3) RMQ: R [u] ≥ R [v] 시 LCA [T, u, v] = RMQ (L, R [v], R [u]);그렇지 않 으 면 LCA [T, u, v] = RMQ (L, R [u], R [v]), RMQ 를 계산한다.
RMQ 에서 사용 하 는 ST 알고리즘 은 온라인 알고리즘 이기 때문에 이 알고리즘 도 온라인 알고리즘 이다.
[예시 설명]
T = < V, E >, 그 중 V = {A, B, C, D, E, F, G}, E = {AB, AC, BD, BE, EF, EG}, 그리고 A 는 나무 뿌리 입 니 다.그림 T 의 DFS 결 과 는 A - > B - > D - > B - > E - > F - > E - > G - > E - > B - > A - > C - > A 로 D 와 G 의 최근 공공 조상 을 요구 하면 LCA [T, D, G] = RMQ (L, R [D], R [G]) = RMQ (L, 3, 8), L 중 4 번 째 에서 7 번 째 원소 의 깊이 는 각각 1, 2, 3, 3 으로 깊이 가 가장 작은 것 은 B 이다.
오프라인 알고리즘 (Tarjan 알고리즘) 설명:
오프라인 알고리즘 이란 모든 문의 (LCA 를 한 번 구 하 는 것 을 한 번 문의 라 고 함) 를 먼저 읽 고 더 효율 적 인 처리 방법 을 얻 기 위해 조회 처리 순 서 를 재 구성 하 는 것 을 말한다.Tarjan 알고리즘 은 LCA 문 제 를 해결 하 는 데 흔히 볼 수 있 는 오프라인 알고리즘 으로 깊이 우선 스 트 리밍 과 검색 집합 을 결합 하여 전체 알고리즘 을 선형 처리 시간 으로 합 니 다.
Tarjan 알고리즘 은 집합 을 기반 으로 하고 우수한 시공 간 복잡 도 를 이용 하여 수집 하여 LCA 문제 의 O (n + Q) 알고리즘 을 실현 할 수 있 습 니 다. 여기 서 Q 는 문의 횟수 를 표시 합 니 다.집합 에 관 한 더 많은 자 료 는 이 글 을 읽 을 수 있다.
이전 알고리즘 과 마찬가지 로 Tarjan 알고리즘 도 깊이 우선 검색 을 사용 해 야 합 니 다. 알고리즘 은 대체적으로 다음 과 같 습 니 다. 새로 검색 한 노드 에 대해 먼저 이 노드 로 구 성 된 집합 을 만 든 다음 에 현재 노드 의 모든 하위 트 리 를 검색 하고 모든 하위 트 리 를 검색 할 때마다 하위 트 리 안의 LCA 문의 가 해결 되 었 음 을 확인 할 수 있 습 니 다.다른 LCA 가 묻 는 결 과 는 반드시 이 자나무 밖 에 있 을 것 이다. 이때 자나무 가 형성 한 집합 과 현재 결점 의 집합 을 합 쳐 현재 결점 을 이 집합의 조상 으로 설정한다.현재 노드 의 모든 하위 트 리 가 검색 될 때 까지 다음 나 무 를 계속 검색 하 세 요.이 때 현재 노드 도 검 사 된 것 으로 설정 하고 현재 노드 와 관련 된 LCA 문 의 를 처리 할 수 있 습 니 다. 현재 노드 에서 노드 v 까지 의 문의 가 있 고 v 가 검 사 된 적 이 있 으 면 깊이 우선 검색 을 하기 때문에 현재 노드 와 v 의 최근 공공 조상 은 검 사 를 받 지 않 았 을 것 입 니 다.최근 에 공공 조상 을 포함 한 v 의 자 수 는 이미 검색 을 했 을 것 이다. 그러면 이 최근 에 공공 조상 은 반드시 v 가 모인 조상 일 것 이다.

     ：

LCA(u)   
{   
     Make-Set(u)   
     ancestor[Find-Set(u)]=u   
       u      v   
     {   
         LCA(v)   
         Union(u,v)   
         ancestor[Find-Set(v)]=u   
       }   
       checked[u]=true  
         (u,v)  P // (u,v)         
     {   
         if checked[v]=true  
 
        then {  
                       u v        ancestor[Find-Set(v)]   
              }   
      }   
}

[예 를 들 어 설명] 실현 알고리즘 을 통 해 알 수 있 듯 이 특정한 나무 가 모두 옮 겨 다 니 며 처리 한 후에 야 이 나무의 뿌리 노드 를 검은색 (초기 화 는 흰색) 으로 표시 하고 프로그램 이 위의 나무 구조 에 따라 옮 겨 다 닌 다 고 가정 한다. 먼저 노드 1 부터 시작 한 다음 에 뿌리 가 2 인 자 나 무 를 재 귀적 으로 처리 하고 자 나 무 를 2 로 처리 한 후에 노드 2, 5, 6 은 모두 검은색 이다.그 다음 에 세 개의 나 무 를 거 슬러 올 라 가 처리 해 야 한다. 먼저 검 게 물 든 것 은 노드 7 (노드 7 은 잎 으로 깊이 검색 하지 않 고 직접 처리 하기 때 문) 이다. 그 다음 에 노드 7 은 모든 문의 (7, x) 의 노드 를 볼 것 이다. 만약 에 존재 한다 면 (7, 5) 노드 5 는 검 게 물 들 었 기 때문에 단정 할 수 있다 (7, 5) 의 최근 공공 조상 은 find (5). ancestor, 즉 노드 1 이다.(2 개의 트 리 처리 가 끝 난 후, 하위 트 리 2 와 노드 1 은 유 니 온 을 진행 하 였 기 때문에, find (5) 는 합 쳐 진 나무의 뿌리 1 을 되 돌려 주 었 습 니 다. 이때 나무 뿌리의 ancestor 값 은 1 입 니 다. (7, 5) 없 으 면 (5, 7) 어떻게 처리 하 는 지 물 어 보 는 사람 이 있 습 니 다. 프로그램 초기 화 할 때 기 교 를 만들어 서 (a, b) 와 (b, a) 에 대해 물 어 볼 수 있 습 니 다.모두 저장 하면 완전 성 을 보장 할 수 있 습 니 다.  LCA 와 RMQ 문 제 를 정리 하 는 것 은 두 가지 매우 기본 적 인 문제 입 니 다. 많은 복잡 한 문제 들 이 이 두 가지 문 제 를 해결 할 수 있 습 니 다. 이 두 가지 문 제 는 ACM 프로 그래 밍 경기 에서 특히 많이 발생 합 니 다. 이 두 가지 문제 의 해결 방법 은 매우 기본 적 인 데이터 구조 와 알고리즘 을 많이 사용 합 니 다. 이 는 집합, 깊이 우선 옮 겨 다 니 기, 동적 계획 등 을 포함 합 니 다.  참고 자료 (1)       두 개의 링크 가 교차 하 는 지 판단 하기 (2)      블 로그 'LCA 문제 (RMQ 포함 ST 알고리즘)' (3)       박문 (4)      블 로그 'LCA 문제 (최근 공공 조상 문제) + RMQ 문제' (5)      박문 '최근 공공 조상 (LCA) 의 Tarjan 알고리즘' (6)       박문 《 LCA 최근 공공 조상의 Tarjan 알고리즘 》
다음은 상술 한 사상 에 대한 실현 이다.
이상 은 RMQ 알고리즘 이 고 RMQ 알고리즘 을 사용 하여 LCA 문 제 를 해결 합 니 다.
오프라인 알고리즘 Tarjan 알고리즘 이후 단독 구현.