Запрос диапазона (структуры данных) - Range query (data structures)

Для поиска предметов, попадающих в диапазон, см. запрос диапазона (база данных).

В структуры данных, а запрос диапазона состоит из предварительной обработки некоторых входных данных в структура данных чтобы эффективно ответить на любое количество запросов на любом подмножестве входных данных. В частности, есть группа проблем, которые были тщательно изучены, когда входом является множество несортированных чисел, а запрос состоит из вычисления некоторой функции, например минимума, в определенном диапазоне массива.

Определение

Запрос диапазона ${\displaystyle q_{f}(A,i,j)}$ на массиве ${\displaystyle A=[a_{1},a_{2},..,a_{n}]}$ из п элементы некоторого набора S, обозначенный ${\displaystyle A[1,n]}$, принимает два индекса ${\displaystyle 1\leq i\leq j\leq n}$, функция ж определены над массивами элементов S и выходы ${\displaystyle f(A[i,j])=f(a_{i},\ldots ,a_{j})}$.

Например, для ${\displaystyle f=\sum }$ и ${\displaystyle A[1,n]}$ массив чисел, запрос диапазона ${\displaystyle \sum _{i,j}A}$ вычисляет ${\displaystyle \sum A[i,j]=(a_{i}+\ldots +a_{j})}$, для любого ${\displaystyle 1\leq i\leq j\leq n}$. На эти вопросы можно ответить в постоянное время и используя ${\displaystyle O(n)}$ дополнительное пространство, вычислив суммы первых я элементы А и сохраняя их во вспомогательном массиве B, так что ${\displaystyle B[i]}$ содержит сумму первых я элементы А для каждого ${\displaystyle 0\leq i\leq n}$. Следовательно, на любой запрос можно ответить, выполнив ${\displaystyle \sum A[i,j]=B[j]-B[i-1]}$.

Эта стратегия может быть расширена для каждого группа оператор ж где понятие ${\displaystyle f^{-1}}$ хорошо определен и легко вычислим.^[1] Наконец, это решение может быть распространено на двумерные массивы с аналогичной предварительной обработкой.^[2]

Примеры

Полугрупповые операторы

Минимальный запрос диапазона сводится к наименьший общий предок проблема.

Основная статья: Минимальный запрос диапазона

Когда интересующая функция в запросе диапазона является полугруппа оператор, понятие ${\displaystyle f^{-1}}$ не всегда определяется, поэтому стратегия из предыдущего раздела не работает. Эндрю Яо показал^[3] что существует эффективное решение для запросов диапазона, которые включают операторы полугруппы. Он доказал, что для любой постоянной c, предварительная обработка времени и пространства ${\displaystyle \theta (c\cdot n)}$ позволяет отвечать на запросы диапазона в списках, где ж является полугрупповым оператором в ${\displaystyle \theta (\alpha _{c}(n))}$ время, где ${\displaystyle \alpha _{k}}$ есть некоторая функциональная инверсия Функция Аккермана.

Есть несколько полугрупповых операторов, которые допускают несколько лучшие решения. Например, когда ${\displaystyle f\in \{\max ,\min \}}$. Предполагать ${\displaystyle f=\min }$ тогда ${\displaystyle \min(A[1..n])}$ возвращает индекс минимум элемент ${\displaystyle A[1..n]}$. потом ${\displaystyle \min _{i,j}(A)}$ обозначает соответствующий запрос минимального диапазона. Существует несколько структур данных, которые позволяют ответить на минимальный запрос диапазона в ${\displaystyle O(1)}$ время с предварительной обработкой времени и пространства ${\displaystyle O(n)}$. Одно из таких решений основано на эквивалентности этой проблемы и наименьший общий предок проблема.

В Декартово дерево ${\displaystyle T_{A}}$ массива ${\displaystyle A[1,n]}$ имеет как корень ${\displaystyle a_{i}=\min\{a_{1},a_{2},\ldots ,a_{n}\}}$ а в качестве левого и правого поддеревьев декартово дерево ${\displaystyle A[1,i-1]}$ и декартово дерево ${\displaystyle A[i+1,n]}$ соответственно. Минимальный запрос диапазона ${\displaystyle \min _{i,j}(A)}$ это наименьший общий предок в ${\displaystyle T_{A}}$ из ${\displaystyle a_{i}}$ и ${\displaystyle a_{j}}$. Поскольку наименьший общий предок может быть решен в постоянное время с использованием предварительной обработки времени и пространства ${\displaystyle O(n)}$, запрос минимального диапазона также может. Решение, когда ${\displaystyle f=\max }$ аналогично. Декартовы деревья могут быть построены в линейное время.

Режим

Основная статья: Запрос в режиме диапазона

В Режим массива А это элемент, который чаще всего появляется в А. Например, режим ${\displaystyle A=[4,5,6,7,4]}$ является 4. В случае ничьей в качестве режима может быть выбран любой из наиболее частых элементов. Запрос в режиме диапазона состоит из предварительной обработки ${\displaystyle A[1,n]}$ так что мы можем найти режим в любом диапазоне ${\displaystyle A[1,n]}$. Для решения этой проблемы было разработано несколько структур данных, некоторые из результатов мы суммируем в следующей таблице.^[1]

Запросы в режиме диапазона

Космос	Время запроса	Ограничения
${\displaystyle O(n^{2-2\epsilon })}$	${\displaystyle O(n^{\epsilon }\log n)}$	${\displaystyle 0\leq \epsilon \leq {\frac {1}{2}}}$
${\displaystyle O\left({\frac {n^{2}\log \log n}{\log n}}\right)}$	${\displaystyle O(1)}$

Недавно Jørgensen et al. доказал нижнюю оценку модель клетки-зонда из ${\displaystyle \Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)}$ для любой структуры данных, которая использует S клетки.^[4]

Медиана

Этот частный случай представляет особый интерес, поскольку нахождение медиана имеет несколько приложений.^[5] С другой стороны, проблема медианы, частный случай проблема выбора, разрешима в О(п), с использованием медиана медиан алгоритм.^[6] Однако его обобщение через средние по диапазону запросов произошло недавно.^[7] Запрос медианного диапазона ${\displaystyle \operatorname {median} (A,i,j)}$ куда А, я и j иметь обычные значения возвращает средний элемент ${\displaystyle A[i,j]}$. Эквивалентно, ${\displaystyle \operatorname {median} (A,i,j)}$ должен вернуть элемент ${\displaystyle A[i,j]}$ ранга ${\displaystyle {\frac {j-i}{2}}}$. Запросы с медианным диапазоном не могут быть решены с помощью любого из описанных выше методов, включая подход Яо для полугрупповых операторов.^[8]

Были изучены два варианта этой проблемы: не в сети версия, где все k интересующие запросы выдаются пакетно, и в версии, где вся предварительная обработка выполняется заранее. Автономную версию можно решить с помощью ${\displaystyle O(n\log k+k\log n)}$ время и ${\displaystyle O(n\log k)}$ Космос.

Следующий псевдокод алгоритм быстрого выбора показывает, как найти элемент ранга р в ${\displaystyle A[i,j]}$ несортированный массив отдельных элементов, чтобы найти установленные нами медианы диапазона ${\displaystyle r={\frac {j-i}{2}}}$.^[7]

rangeMedian (A, i, j, r) { если A.length () == 1 возвращаться А [1] если A.low не определено тогда        m = медиана (A) A.low = [e в A | e <= m] A.high = [e in A | e> m] вычисляет t количество элементов A [i, j], принадлежащих A.low если г <= т тогда        возвращаться rangeMedian (A.low, i, j, r) еще        возвращаться rangeMedian (A.high, i, j, r-t)}

Процедура rangeMedian перегородки А, с помощью Амедиана на два массива A.low и Высота, где первые содержат элементы А которые меньше или равны медиане м а последнее - остальные элементы А. Если мы знаем, что количество элементов ${\displaystyle A[i,j]}$ это продвигается в A.low является т и это число больше чем р то мы должны продолжать искать элемент ранга р в A.low; в противном случае нужно искать элемент ранга ${\displaystyle (r-t)}$ в Высота. Найти т, достаточно найти максимальный индекс ${\displaystyle m\leq i-1}$ такой, что ${\displaystyle a_{m}}$ в A.low и максимальный индекс ${\displaystyle l\leq j}$ такой, что ${\displaystyle a_{l}}$в Высота. потом ${\displaystyle t=l-m}$. Общая стоимость любого запроса без учета части разделения составляет ${\displaystyle \log n}$ поскольку самое большее ${\displaystyle \log n}$ рекурсивные вызовы выполняются, и в каждом из них выполняется только постоянное количество операций (чтобы получить значение т дробное каскадирование Если используется линейный алгоритм для поиска медиан, общая стоимость предварительной обработки для k диапазон медианных запросов ${\displaystyle n\log k}$. Алгоритм также можно модифицировать для решения онлайн версия проблемы.^[7]

Связанные проблемы

Все проблемы, описанные выше, были изучены как для более высоких размерностей, так и для их динамических версий. С другой стороны, запросы диапазона могут быть расширены на другие структуры данных, такие как деревья,^[8] такой как проблема предка уровня. Аналогичное семейство проблем ортогональный диапазон запросы, также известные как подсчетные запросы.

Смотрите также

• Проблема предка уровня
• Самый низкий общий предок

Рекомендации

1. Крижанц, Дэнни; Морен, Пат; Смид, Михил Х. М. (2003). «Запросы режима диапазона и среднего диапазона для списков и деревьев». ИСААК: 517–526.
2. Мэн, Хэ; Манро, Дж. Ян; Николсон, Патрик К. (2011). «Выбор динамического диапазона в линейном пространстве». ИСААК: 160–169.
3. Яо, A.C (1982). «Пространственно-временной компромисс для ответа на запросы диапазона». е 14-й ежегодный симпозиум ACM по теории вычислений: 128–136.
4. Греве, М; J { o} rgensen, A .; Ларсен, К .; Труэльсен, Дж. (2010). «Нижние границы клеточного зонда и приближения для режима дальности». Автоматы, языки и программирование: 605–616.
5. Хар-Пелед, Сариэль; Мутукришнан, С. (2008). «Медианы диапазона». ЕКА: 503–514.
6. Блюм, М.; Флойд, Р. В.; Пратт, В.; Ривест, Р. Л.; Тарьян, Р.Э. (Август 1973 г.). «Сроки отбора» (PDF). Журнал компьютерных и системных наук. 7 (4): 448–461. Дои:10.1016 / S0022-0000 (73) 80033-9.
7. Бит, Гфеллер; Сандерс, Питер (2009). «К оптимальному среднему диапазону». ИКАЛП (1): 475–486.
8. Бозе, П.; Kranakis, E .; Морен, П.; Тан, Ю. (2005). «Примерный режим диапазона и медианное значение диапазона запросов». В Трудах 22-го симпозиума по теоретическим аспектам информатики (STACS 2005), том 3404 конспектов лекций по компьютерным наукам: 377–388.

внешняя ссылка

• Структура открытых данных - Глава 13 - Структуры данных для целых чисел
• Структуры данных для запросов Range Median - Герт Столтинг Бродал и Аллан Гронлунд Йоргенсен