이런 종류의 RMQ를위한 가장 빠른 알고리즘은 무엇입니까? 이전이 <code>A[i]</code> 전류를 계산하기 위해 <code>A[j]</code>을 계산의

Question

나는 다음과 같은 알고리즘을 사용하여 작업을하고있는 중이 야 (의사 코드)을하려고 루프가 무엇

int A = [] 
int C = { ... } // N non-negative integers 
int R = { ... } // N non-negative integers 
for(i = 0 to N){ 
    // Let j in range [i-R[i], i-1] 
    A[i] = Minimum of (A[j] + C[j]) where j in [i-R[i], i-1] 
} 

는 범위를 사용합니다.

N 동적 RMQ (범위 최소 쿼리)를 수행하는 것과 같습니다.

사전에 A의 값을 모르기 때문에 동적입니다. 이전에 계산 된 값을 사용하여 온라인으로 계산합니다. 예를 들어

---

,

C = {10,1,5,3} 
R = {2,4,2,3} 

A[0] = C[0] // Assume for i = 0, this is always true as base case 
A[1] = Min(A[j] + C[j]) where -3 <= j <= 0, only j = 0 is valid option 
    = Min(A[0] + C[0]) = 20 
A[2] = Min(A[j] + C[j]) where 1 <= j <= 1 
    = 21 
A[3] = Min(A[j] + C[j]) where -1 <= j <= 2 
    = Min(A[0]+C[0], A[1]+C[1], A[2]+C[2]) 
    = Min(20, 21, 24) 
    = 20 

---

그래서 제 질문은,이를 달성하기 위해 O(N^2)보다 빠른 어떤 알고리즘이있다

? 어떤 메소드/데이터 구조가 N RMQ 속도를 높이는 것처럼 느껴지지만 어떻게해야할지 모르겠다.

예제가 명확하지 않으면 자세히 설명해주십시오.

Answer 1

동적 RMQ 문제는 쿼리 당 복잡도가 O(log n) 인 segment tree의 기본 응용 프로그램입니다.