Диапазон среднего запроса в массиве за O (1) времени с использованием предварительной обработки

Question

В классе мы узнали о проблемах RMQ-LCA-RMQ и о том, как поддерживать минимальный запрос диапазона операций за время O (1).В качестве упражнения мой профессор назначил меня для поддержки операции: средний запрос диапазона в пространстве O (n), время предварительной обработки O (n) и время выбора O (1).

Допустим, у меня есть массив Aсодержит 8, 7, 9, 2, 6, 4, 5, 3. Учитывая медиану (i, j), мы должны получить медиану между i-м и j-м элементами (включительно) после сортировки массива.Отсортировано 2, 3, 4, 5, 6, 7, 8, 9. Например, медиана (2,6) = A [4] = 6 (потому что медиана 4, 5, 6, 7, 8 - 6).

Я нашел другие решения, которые предлагают использовать деревья сегментов, но сложность не O (1) в этих случаях.Можно ли решить эту проблему таким же образом, как мы решаем проблему RMQ to LCA to RMQ?

Answer 1

Одним из вариантов будет использование не сравнительного алгоритма сортировки. Известные примеры: radix sort (O(wn), где w - размер слова) и счетная сортировка (O(n+k), где k - максимальное значение ключа ). Оба они являются линейными относительно размера ввода.

Затем вы можете просто найти правильную позицию в списке, что является O(1) операцией. Оба метода сортировки соответствуют вашим требованиям - сортировка по основанию равна O(n+k), а сортировка по подсчету - O(k).

Answer 2

Это невозможно при сравнении.Если бы это было так, вы могли бы сравнить сортировку N элементов за O (N) времени, предварительно обработав входную и вычисляя медиану (i, i) для каждого i от 0 до N-1.