Как найти минимальный или максимальный элемент в области матрицы?

Это зависит от того, что вы подразумеваете под «наиболее эффективным способом». Можно минимизировать само время запроса, время предварительной обработки или требования к памяти.

Если нужно свести к минимуму только время запроса, «наиболее эффективным способом» является предварительное вычисление всех возможных областей. Затем каждый запрос обрабатывается путем возврата некоторого предварительно вычисленного значения. Время запроса O(1). И память, и время предварительной обработки огромны: O((NM)²).

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

Просто подготовьте таблицу из всех прямоугольников со степенью двойки длины и высоты со степенью двойки и используйте четыре из этих прямоугольников для обработки любого запроса на минимальный диапазон. В результате получается как минимум четыре минимальных значения для каждого из этих прямоугольников. Время запроса O(1). Память и время предварительной обработки составляют O(NM*log(N)*log(M)).

Этот документ: "Двумерные запросы минимального диапазона" Amihood Amir , Йоханнес Фишер и Моше Левенштейн предлагают, как уменьшить требования к памяти и время предварительной обработки для этого алгоритма почти до O(MN).

Эта статья: "Структуры данных для запросов минимального диапазона в многомерных массивах" Хао Юань и Михаил Дж. Аталлах дает другой алгоритм с временем запроса O (1) и памятью O (NM) и временем предварительной обработки.

Не имея никакой другой информации о содержании матрицы или о том, как она хранится, невозможно сделать какое-либо предложение, кроме как просто просмотреть каждую запись в данном регионе. Это O((x2-x1) * (y2-y1)). Ваш вопрос слишком расплывчатый, чтобы сказать что-то еще.

Возможно, вы могли бы сделать лучше (вероятностно, в среднем случае), если бы вы знали что-то еще о матрице, например, если бы вы знали, что элементы, вероятно, каким-то образом отсортированы.

Псевдокод:

function getMax(M, x1, x2, y1, y2)
    max = M[x1,y1]
    for x = x1 to x2 do
        for y = y1 to y2 do
            if M[x,y] > max then max = M[x, y]
    return max

Это O (n) в размере ввода, который можно разумно интерпретировать только как размер области матрицы (x2 - x1) * (y2 - y1). Если вам нужен минимум, измените max на min и > на ‹. Вы не можете сделать лучше, чем O(n), т.е. проверить каждый из возможных элементов. Предположим, у вас есть алгоритм, который работает быстрее, чем O(n). Тогда он не проверяет все элементы. Чтобы получить неверный случай для алгоритма, возьмите один из элементов, который он не проверяет, и замените его на (max + 1) и повторно запустите алгоритм.