algorithm - 这种 RMQ 最快的算法是什么？

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]
}

循环试图做的是，使用一系列先前计算的 A[j] 来计算当前的 A[i]。

对我来说，这就像做 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问题是segment tree的基本应用，每个查询的复杂度为 O(log n)。