Сложность единичного изменения в массиве, которое поддерживается статическим Range Minimum Query

Question

У меня был тест в курсе структур данных, и один из вопросов был:

Допустим, у вас есть массив n-размера, который поддерживается с помощью запроса минимального диапазона, который дает минимум между двумя числами в массиве в o(1) сложности. Конечно, массив был подготовлен, чтобы ответить на RMQ, используя динамическое программирование для различных опций. Вопрос в том, что если я изменю один объект (число) в массиве, как бы я изменил подготовленные мной действия, чтобы я все еще мог найти RMQ в o(1), и какую сложность это займет.

ответ не делает новый RMQ в o(n), он должен быть меньше этого.

этот вопрос не домашнее задание, я просто хочу пройти тест, чтобы понять.

заранее спасибо.

Answer 1

Сохраните индекс I и новое значение V элемента изменилось.

Получив запрос [L,R], проверьте, если L <= I <= R, если это так, верните минимум old_rmq(L,R) и V.

Answer 2

На самом деле есть три типа алгоритмов для RMQ на основе сложности для update а также query:

   Update     Query
1. O(N)       O(1)
2. O(1)       O(N)
3. O(logN)    O(logN)

Алгоритмы первого и второго типов довольно просты в реализации. Первый включает в себя сохранение значений для всех возможных запросов и, таким образом, ответы на них в O(1) время. Второй включает в себя только обновление структуры данных в O(1) время, но запрос требует O(N), По вашему вопросу, невозможно иметь такую ​​комбинацию.

Однако третий тип алгоритмов представляет особый интерес. Если вы ослабите условие, которое может выполнить запрос O(logN) время, а не O(1)У вас также будет преимущество, когда общее время выполнения остается постоянным независимо от количества обновлений и запросов.

AFAIK, лучшими структурами данных, используемыми для получения таких времен выполнения, являются дерево сегментов и деревья с двоичными индексами