Какой самый быстрый алгоритм для такого рода 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 RMQs, но я не знаю, как.

Пожалуйста, скажите мне, чтобы уточнить, если пример не ясен.

Answer 1

Проблема динамического RMQ - это базовое приложение дерева сегментов, со сложностью O(log n) за запрос.