Быстрый поиск максимума-минимума

Не совсем корректно задан вопрос. Если длина строго ограничена, то формально простой перебор элементов массива на любом интервале будет работать за O(1) . Будем считать, что предполагается сложность от числа элементов и информацию об ограничении длины массива мы в оценке сложности не используем. Тогда данная задача состоит из препроцессинга данных и собственно ответов на запросы о минимумах и максимумах. Соответственно, чем больше сложность препроцессинга, тем эффективнее можно давать ответы на запросы, и наоборот. Всё зависит от используемой структуры данных.

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

Соответственно истину надо искать в золотой середине между сложностью препроцессинга и ответов на запросы. Золотая середина не даст ни по одному из этих пунктов O(1). Основные структуры данных, которые можно посоветовать для эффективного баланса - это дерево отрезков, либо матрица размера NxlogN с вспомогательными результатами. Эти структуры очень хорошо описаны вот тут, так что не буду заниматься копипастом. Удачного изучения! А вообще ключевое слово: RMQ (Range Minimum Query).