В структурах данных , A - запрос диапазон состоит из предварительной обработки некоторых входных данных в структуру данных , чтобы эффективно ответить на любое количество запросов на любом подмножестве входных данных. В частности, существует группа проблем, которые были тщательно изучены, когда входными данными является массив несортированных чисел, а запрос состоит из вычисления некоторой функции, например минимума, в определенном диапазоне массива.
Определение
Запрос диапазона на массиве из n элементов некоторого множества S , обозначаемого, принимает два индекса , функция f, определенная над массивами элементов S и выходами.
Например, для а также массив чисел, запрос диапазона вычисляет , для любой . На эти запросы можно ответить в постоянное время и с помощьюдополнительное пространство, вычисляя суммы первых i элементов массива A и сохраняя их во вспомогательном массиве B , так чтосодержит сумму первых i элементов A для каждого. Следовательно, на любой запрос можно ответить, выполнив.
Эта стратегия может быть расширена для любого группового оператора f, в котором понятиехорошо определен и легко вычислим. [1] Наконец, это решение может быть расширено до двумерных массивов с аналогичной предварительной обработкой. [2]
Примеры
Полугрупповые операторы
Когда интересующая функция в запросе диапазона является оператором полугруппы , понятиене всегда определяется, поэтому стратегия из предыдущего раздела не работает. Эндрю Яо показал [3], что существует эффективное решение для запросов диапазона, в которых используются полугрупповые операторы. Он доказал, что для любой постоянной c предварительная обработка времени и пространствапозволяет отвечать на запросы диапазона в списках, где f - оператор полугруппы в время, где - некоторая функциональная инверсия функции Аккермана .
Есть некоторые полугрупповые операторы, допускающие несколько лучшие решения. Например, когда. Предполагать тогда возвращает индекс минимального элемента. потомобозначает соответствующий запрос минимального диапазона. Существует несколько структур данных, которые позволяют ответить на минимальный запрос диапазона в время с предварительной обработкой времени и пространства . Одно из таких решений основано на эквивалентности этой проблемы и проблемы наименьшего общего предка .
Декартово дерево массива имеет как корень а в качестве левого и правого поддеревьев декартово дерево и декартово дерево соответственно. Минимальный запрос диапазонаявляется самым низким общим предком в из а также . Поскольку наименьший общий предок может быть решен за постоянное время, используя предварительную обработку времени и пространства., запрос минимального диапазона также может. Решение, когдааналогично. Декартовы деревья можно построить за линейное время .
Режим
Режим массива A представляет собой элемент , который появляется наиболее A . Например, режим является 4 . В случае ничьей в качестве режима может быть выбран любой из наиболее частых элементов. Запрос в режиме диапазона состоит из предварительной обработки так что мы можем найти режим в любом диапазоне . Для решения этой проблемы было разработано несколько структур данных, некоторые из результатов мы суммируем в следующей таблице. [1]
Космос | Время запроса | Ограничения |
---|---|---|
Недавно Jørgensen et al. остававшаяся нижняя граница модели клеточного зонда издля любой структуры данных, использующей S- ячейки. [4]
Медиана
Этот частный случай представляет особый интерес, поскольку нахождение медианы имеет несколько приложений. [5] С другой стороны, проблема медианы, частный случай задачи выбора , разрешима за O ( n ), используя алгоритм медианы медиан . [6] Однако его обобщение с помощью запросов с медианой диапазона произошло недавно. [7] Запрос медианного диапазонагде A, i и j имеют обычные значения, возвращает средний элемент. Эквивалентно, должен вернуть элемент ранга . Запросы с медианным диапазоном не могут быть решены с помощью любого из описанных выше методов, включая подход Яо для полугрупповых операторов. [8]
Были изучены два варианта этой проблемы: автономная версия, где все k интересующих запросов задаются в пакете, и версия, в которой вся предварительная обработка выполняется заранее. Автономную версию можно решить с помощью время и космос.
Следующий псевдокод алгоритма быстрого выбора показывает, как найти элемент ранга r в несортированный массив отдельных элементов, чтобы найти медианы диапазона, которые мы установили . [7]
rangeMedian (A, i, j, r) { если A.length () == 1 вернуть A [1] если A.low не определен, то m = медиана (A) A.low = [e в A | e <= m] A.high = [e в A | e> m] вычислить t количество элементов A [i, j], принадлежащих A.low если r <= t, тогда вернуть rangeMedian (A.low, i, j, r) иначе вернуть rangeMedian (A.high, i, j, rt)}
Процедура rangeMedian
разбивает A
с помощью A
медианы на два массива A.low
и A.high
, если первый содержит элементы A
, которые меньше или равны медиане, m
а второй - остальные элементы A
. Если мы знаем, что количество элементовкоторые заканчиваются на A.low
is, t
и это число больше, чем r
мы должны продолжать искать элемент rank r
in A.low
; в противном случае мы должны искать элемент рангав A.high
. Чтобы найти t , достаточно найти максимальный индекс такой, что находится в A.low
и максимальный индекс такой, что находится в A.high
. потом. Общая стоимость любого запроса без учета части разделения составляет поскольку самое большее рекурсивные вызовы выполняются, и в каждом из них выполняется только постоянное количество операций (для получения значения t следует использовать дробное каскадирование ). Если используется линейный алгоритм для поиска медиан, общая стоимость предварительной обработки для медианных запросов диапазона k равна. Алгоритм также может быть изменен для решения онлайн- версии задачи. [7]
Связанные проблемы
Все проблемы, описанные выше, были изучены как для более высоких размерностей, так и для их динамических версий. С другой стороны, в диапазоне запросы могут быть распространены и на другие структуры данных , таких как деревья , [8] , такие как проблемы уровня предка . Аналогичное семейство проблем - это запросы с ортогональным диапазоном , также известные как запросы подсчета.
Смотрите также
Рекомендации
- ^ a b Крижанк, Дэнни; Morin, Pat ; Smid, Michiel HM (2003). «Запросы режима диапазона и среднего диапазона для списков и деревьев» . ISAAC : 517–526. arXiv : cs / 0307034 .
- ^ Мэн, Хэ; Манро, Дж. Ян; Николсон, Патрик К. (2011). «Выбор динамического диапазона в линейном пространстве». ISAAC : 160–169.
- ^ Яо, A.C (1982). "Пространственно-временной компромисс для ответа на запросы диапазона". E 14-й ежегодный симпозиум ACM по теории вычислений : 128–136.
- ^ Греве, М; J {\ o} rgensen, A .; Ларсен, К .; Труэльсен, Дж. (2010). «Нижние границы клеточного зонда и приближения для режима дальности». Автоматы, языки и программирование : 605–616.
- ^ Хар-Пелед, Сариэль ; Мутукришнан, С. (2008). «Медианы диапазона». ESA : 503–514.
- ^ Блюм, М .; Флойд, RW ; Пратт, ВР ; Ривест, Р.Л . ; Тарьян, Р. Э. (август 1973 г.). «Сроки выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. DOI : 10.1016 / S0022-0000 (73) 80033-9 .
- ^ а б в Бит, Гфеллер; Сандерс, Питер (2009). «К оптимальному диапазону медиан». Икалп (1) : 475–486.
- ^ а б Bose, P ; Kranakis, E .; Морин, П .; Тан, Ю. (2005). «Примерный режим диапазона и медианное значение диапазона запросов» . В материалах 22-го симпозиума по теоретическим аспектам информатики (STACS 2005), том 3404 конспектов лекций по компьютерным наукам: 377–388.
Внешние ссылки
- Структура открытых данных - Глава 13 - Структуры данных для целых чисел
- Структуры данных для запросов Range Median - Герт Столтинг Бродал и Аллан Гронлунд Йоргенсен