Нахождение минимального числа в данном сегменте массива

Question

Допустим, у нас есть большой массив целых чисел A. Мы хотим ответить на многие запросы, например:

• Найти минимум между индексами 0 и 100
• Найти минимум междуиндексы 4 и 90
• ...

Пример: A = {6, 1, 7, 5, 3}

• мин между индексами 0и 1 равно 1
• мин между индексами 2 и 3 равно 5
• мин между индексами 0 и 4 равно 1

Очевидный способ обхода элементов для каждогозапрос и поиск минимума не достаточно в отношении производительности.Мне как-то нужно хранить необходимую информацию за один проход, а затем отвечать на запросы в постоянное время.Поэтому алгоритм не должен быть квадратичным.Нужно что-то лучше, чем O (N * M).(N: размер массива, M: количество запросов)

Я пытался, но не мог найти, как это сделать.Это должно быть что-то о поиске и хранении некоторых сумм и как-то их использовать.Есть идеи?Спасибо за чтение.

Answer 1

Два варианта для рассмотрения:

1. O (n) предварительных вычислений и O (logn) на запрос
2. O (nlogn) предварительное вычисление и O (1) на запрос

Сначала работает, рекурсивно вычисляя минимум для всех пар в четных точках, затем все 4 в точках, кратных 4, затем все 8 во всех кратных 8 и так далее. Затем, когда вы хотите получить доступ к минимуму для определенного диапазона, вы разбиваете его на части, которые у вас уже есть, и вычисляете минимум из них.

Например, чтобы найти минимум элементов 1..10, вы используете минимум 1 и 2..3 и 4..7 и 8..9 и 10.

Вторая работает, вырабатывая минимум для всех пар во ВСЕХ местах, затем все 4 во ВСЕХ местах, затем все 8 во ВСЕХ местах. Когда у вас есть определенный диапазон, вы строите его как минимум из двух частей и вычисляете минимум из этих двух.

Например, чтобы найти минимум элементов 1..10, вы используете минимум 1..8 в сочетании с минимумом 3..10.

Answer 2

Для каждого вопроса сделайте «решение», «мин» и «макс»

Затем при переходе к следующему элементу массива, если вы достигнете индекса == мин вопроса, решение = номер этого индекса.И пока вы не достигли максимума, вы сравниваете решение с числом в этом индексе и фактическим решением.(Хорошо, я понял, когда писал, что это n * m, извините)