I am doing a task using the following algorithm (pseudo code)
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]
}
What the loop trying to do is, use a range of previous computed A[j]
to compute current A[i]
.
To me it is like doing N dynamic RMQs (Range minimum query).
It is dynamic because we do not know the value of A
beforehand, we compute it online using the previously computed values.
For example,
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
So my question is, is there any algorithm which is faster than O(N^2)
to achieve this? I feel like there is some method / data structure to speed up the N
RMQs, but I do not know how.
Please tell me to elaborate more if the example is not clear.
dynamic RMQ problem is a basic application of segment tree, with complexity
O(log n)
per query.