Запрос диапазона (информатика)

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

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

Определение

Дана функция $f$ который принимает массив, запрос диапазона $f_{q}(l,r)$ в массиве $a=[a_{1},..,a_{n}]$ принимает два индекса $l$ и $r$ и возвращает результат $f$ при применении к подмассиву $[a_{l},\ldots ,a_{r}]$. Например, для функции $\operatorname {sum}$ который возвращает сумму всех значений в массиве, запрос диапазона $\operatorname {sum} _{q}(l,r)$ возвращает сумму всех значений в диапазоне $[l,r]$.

Решения

Массив сумм префиксов

Основная статья: Сумма префикса

На запросы суммы диапазона можно ответить в постоянное время и линейное пространство путем предварительного вычисления массива p той же длины, что и входные данные, так что для каждого индекса i элемент p _i является суммой первых i элементов a . Любой запрос может быть вычислен следующим образом: $$\operatorname {sum} _{q}(l,r)=p_{r}-p_{l-1}.$$

Эту стратегию можно распространить на любую другую бинарную операцию. $f$ чья обратная функция $f^{-1}$ корректно определено и легко вычислимо. Его также можно расширить до более высоких измерений с помощью аналогичной предварительной обработки. Например, если p _i,j содержит сумму первых i × j элементов a , то $$\operatorname {sum} _{q}(l,r,t,b)=p_{r,b}-p_{l-1,b}-p_{r,t-1}+p_{l-1,t-1}.$$

Запросы динамического диапазона

Более сложная часть проблемы состоит в выполнении запросов диапазона к динамическим данным; то есть данные, которые могут изменяться между каждым запросом. Для эффективного обновления значений массива более сложные структуры данных, такие как дерево сегментов или дерево Фенвика . необходимы

Примеры

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

Запрос минимального диапазона сведен к проблеме наименьшего общего предка .

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

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

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

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

Режим

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

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

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

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

Недавно Йоргенсен и др. доказал нижнюю границу клеточного зонда модели $\Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)$ для любой структуры данных, использующей S- ячейки.

медиана

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

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

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

rangeMedian(A, i, j, r) {
    if A.length() == 1
        return A[1]

    if A.low is undefined then
        m = median(A)
        A.low  = [e in A | e <= m]
        A.high = [e in A | e > m ]

    calculate t the number of elements of A[i, j] that belong to A.low

    if r <= t then
        return rangeMedian(A.low, i, j, r)
    else
        return rangeMedian(A.high, i, j, r-t)
}

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

Большинство

Поиск часто встречающихся элементов в заданном наборе элементов — одна из наиболее важных задач интеллектуального анализа данных. Поиск часто встречающихся элементов может оказаться сложной задачей, поскольку большинство элементов имеют схожие частоты. Следовательно, было бы более полезно, если бы для обнаружения таких предметов использовался некоторый порог значимости. Один из самых известных алгоритмов поиска большей части массива был предложен Бойером и Муром. который также известен как алгоритм большинства голосов Бойера-Мура . Бойер и Мур предложили алгоритм поиска мажоритарного элемента строки (если он есть) в $O(n)$ время и использование $O(1)$ космос. В контексте работы Бойера и Мура и вообще говоря, мажоритарным элементом в наборе элементов (например, строке или массиве) является элемент, количество экземпляров которого превышает половину размера этого набора. Несколько лет спустя Мисра и Грис предложил более общую версию алгоритма Бойера и Мура, используя $O\left(n\log \left({\frac {1}{\tau }}\right)\right)$ сравнения для поиска всех элементов массива, относительная частота которых превышает некоторый порог $0<\tau <1$. Диапазон $\tau$-мажоритарный запрос — это запрос, который для заданного поддиапазона структуры данных (например, массива) размера $|R|$, возвращает набор всех отдельных элементов, которые появляются больше (или в некоторых публикациях равны) $\tau |R|$ раз в этом заданном диапазоне. В разных структурах, поддерживающих диапазон $\tau$-большинство запросов, $\tau$ может быть статическим (указанным во время предварительной обработки) или динамическим (указанным во время запроса). Многие из таких подходов основаны на том, что независимо от размера диапазона для данного $\tau$ может быть максимум $O(1/\tau )$ отдельные кандидаты с относительной частотой как минимум $\tau$. Проверяя каждого из этих кандидатов в постоянное время, $O(1/\tau )$ достигается время запроса. Диапазон $\tau$-запрос большинства является разложимым в том смысле, что $\tau$-большинство в диапазоне $R$ с перегородками $R_{1}$ и $R_{2}$ должно быть $\tau$-большинство в любом $R_{1}$или $R_{2}$. Из-за этой разложимости некоторые структуры данных отвечают $\tau$-большинство запросов к одномерным массивам путем поиска наименьшего общего предка (LCA) конечных точек диапазона запроса в дереве диапазонов и проверки двух наборов кандидатов (размера $O(1/\tau )$) от каждой конечной точки до наименьшего общего предка за постоянное время, что приводит к $O(1/\tau )$ время запроса.

Двумерные массивы

Гаги и др. предложил структуру данных, которая поддерживает диапазон $\tau$-большинство запросов на $m\times n$ множество $A$. Для каждого запроса $\operatorname {Q} =(\operatorname {R} ,\tau )$ в этой структуре данных порог $0<\tau <1$ и прямоугольный диапазон $\operatorname {R}$ указаны, и набор всех элементов, относительные частоты которых (внутри этого прямоугольного диапазона) больше или равны $\tau$ возвращаются в качестве вывода. Эта структура данных поддерживает динамические пороговые значения (указанные во время запроса) и порог предварительной обработки. $\alpha$ на основе чего он построен. набор вертикальных и горизонтальных интервалов. В ходе предварительной обработки на графике строится $m\times n$ множество. Вместе вертикальный и горизонтальный интервал образуют блок. Каждый блок является частью суперблока, в девять раз большего, чем он сам (в три раза больше горизонтального интервала блока и в три раза больше его вертикального). Для каждого блока набор кандидатов (с ${\frac {9}{\alpha }}$ элементов), который состоит из элементов, имеющих относительные частоты не менее ${\frac {\alpha }{9}}$ (порог предварительной обработки, как упомянуто выше) в соответствующем суперблоке. Эти элементы хранятся в невозрастающем порядке в соответствии с их частотами, и легко видеть, что любой элемент, имеющий относительную частоту не менее $\alpha$ в блоке должен появиться свой набор кандидатов. Каждый $\tau$На запрос -majority сначала отвечают путем нахождения блока запроса или самого большого блока, содержащегося в предоставленном прямоугольнике запроса в $O(1)$ время. Для полученного блока запроса первый ${\frac {9}{\tau }}$ кандидаты возвращаются (без проверки) в $O(1/\tau )$ время, поэтому этот процесс может вернуть некоторые ложные срабатывания. Многие другие структуры данных (как обсуждается ниже) предложили методы проверки каждого кандидата за постоянное время и, таким образом, поддержания $O(1/\tau )$ время запроса, не возвращая ложных срабатываний. Случаи, когда блок запроса меньше, чем $1/\alpha$ обрабатываются путем хранения $\log \left({\frac {1}{\alpha }}\right)$ различные экземпляры этой структуры данных следующего вида:

$\beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}$

где $\beta$ порог предварительной обработки $i$-й экземпляр. Таким образом, для блоков запроса размером менее $1/\alpha$ тот $\lceil \log(1/\tau )\rceil$-ый экземпляр запрошен. Как упоминалось выше, эта структура данных имеет время запроса $O(1/\tau )$ и требует $O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)$ бит пространства, сохраняя его копию, закодированную Хаффманом (обратите внимание на $\log({\frac {1}{\alpha }})$ фактор, а также см. кодирование Хаффмана ).

Одномерные массивы

Чан и др. предложил структуру данных, которая представляет собой одномерный массив $A$, поддиапазон $R$ из $A$ (указывается во время запроса) и пороговое значение $\tau$ (указывается во время запроса), может возвращать список всех $\tau$-большинство в $O(1/\tau )$ время, требующее $O(n\log n)$ слова космоса. Чтобы ответить на такие вопросы, Chan et al. начнем с того, что существует структура данных, способная возвращать k самых частых элементов в диапазоне в $O(k)$ время, требующее $O(n)$ слова космоса. Для одномерного массива $A[0,..,n-1]$, пусть односторонний запрос диапазона top-k имеет вид $A[0..i]{\text{ for }}0\leq i\leq n-1$. Для максимального диапазона диапазонов $A[0..i]{\text{ through }}A[0..j]$ в котором частота отдельного элемента $e$ в $A$ остается неизменным (и равным $f$), строится горизонтальный отрезок. $x$-интервал этого отрезка соответствует $[i,j]$ и у него есть $y$-значение, равное $f$. Поскольку добавление каждого элемента в $A$ меняет частоту ровно одного отдельного элемента, вышеупомянутый процесс создает $O(n)$ отрезки линии. Более того, для вертикальной линии $x=i$ все пересекающие его отрезки горизонтальных линий сортируются по их частотам. Обратите внимание, что каждый горизонтальный отрезок с $x$-интервал $[\ell ,r]$ соответствует ровно одному отдельному элементу $e$ в $A$, такой, что $A[\ell ]=e$. Затем на запрос top-k можно ответить, стреляя вертикальным лучом. $x=i$ и сообщаем о первом $k$ горизонтальные отрезки, которые его пересекают (помните сверху, что эти отрезки уже отсортированы по их частотам) в $O(k)$ время.

Чан и др. сначала постройте дерево диапазонов , в котором каждый узел ветвления хранит одну копию структуры данных, описанной выше для односторонних запросов top-k диапазона, а каждый лист представляет элемент из $A$. Структура данных top-k в каждом узле создается на основе значений, существующих в поддеревьях этого узла, и предназначена для ответа на односторонние запросы top-k диапазона. Обратите внимание, что для одномерного массива $A$, дерево диапазонов можно построить путем деления $A$ на две половины и повторяющиеся на обеих половинах; следовательно, каждый узел результирующего дерева диапазонов представляет собой диапазон. Также можно видеть, что это дерево диапазонов требует $O(n\log n)$ слова пространства, потому что есть $O(\log n)$ уровни и каждый уровень $\ell$ имеет $2^{\ell }$ узлы. Более того, поскольку на каждом уровне $\ell$ дерева диапазонов все узлы имеют в общей сложности $n$ элементы $A$ в их поддеревьях и поскольку существуют $O(\log n)$ уровней, пространственная сложность этого дерева диапазонов равна $O(n\log n)$.

Используя эту структуру, диапазон $\tau$-большинство запросов $A[i..j]$ на $A[0..n-1]$ с $0\leq i\leq j\leq n$ отвечают следующим образом. Во-первых, наименьший общий предок (LCA) листовых узлов. $i$ и $j$ находится в постоянном времени. Обратите внимание, что существует структура данных, требующая $O(n)$ бит пространства, способного отвечать на запросы LCA в $O(1)$ время. Позволять $z$ обозначаем LCA $i$ и $j$, с использованием $z$ и по разложимости диапазона $\tau$-большинство запросов (как описано выше и в ), двусторонний запрос диапазона $A[i..j]$ могут быть преобразованы в два односторонних запроса диапазона top-k (из $z$ к $i$ и $j$). Эти два односторонних запроса top-k диапазона возвращают верхнюю-( $1/\tau$) наиболее частые элементы в каждом из соответствующих диапазонов в $O(1/\tau )$ время. Эти частые элементы составляют набор кандидатов на $\tau$-большинство в $A[i..j]$ в котором есть $O(1/\tau )$ кандидатов, некоторые из которых могут быть ложноположительными. Затем каждый кандидат оценивается в постоянное время с использованием структуры данных линейного пространства (как описано в лемме 3 в ), который способен определить в $O(1)$ время, независимо от того, задан ли данный поддиапазон массива $A$ содержит как минимум $q$ экземпляры определенного элемента $e$.

Тропы деревьев

Гаги и др. предложил структуру данных, которая поддерживает такие запросы, что при наличии двух узлов $u$ и $v$ в дереве, могут сообщить список элементов, которые имеют большую относительную частоту, чем $\tau$ по пути из $u$ к $v$. Более формально, пусть $T$ быть помеченным деревом, в котором каждый узел имеет метку из алфавита размера $\sigma$. Позволять $label(u)\in [1,\dots ,\sigma ]$ обозначаем метку узла $u$ в $T$. Позволять $P_{uv}$ обозначаем уникальный путь от $u$ к $v$ в $T$ в котором средние узлы перечислены в порядке их посещения. Данный $T$и фиксированный (указанный во время предварительной обработки) порог $0<\tau <1$, запрос $Q(u,v)$ должен вернуть набор всех меток, которые появляются более чем $\tau |P_{uv}|$ раз в $P_{uv}$.

Чтобы построить эту структуру данных, сначала ${O}(\tau n)$ узлы отмечены . Это можно сделать, отметив любой узел, расстояние до которого не менее $\lceil 1/\tau \rceil$ от низа трех (высота) и глубина которого делится на $\lceil 1/\tau \rceil$. После этого можно заметить, что расстояние между каждым узлом и его ближайшим отмеченным предком меньше, чем $2\lceil 1/\tau \rceil$. Для отмеченного узла $x$, $\log(depth(x))$ разные последовательности (пути к корню) $P_{i}(x)$ хранятся,

$P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle$

для $0\leq i\leq \log(depth(x))$ где $\operatorname {par} (x)$ возвращает метку прямого родителя узла $x$. Другими словами, для каждого помеченного узла сохраняется набор всех путей длиной в степени двойки (плюс один для самого узла) к корню. Более того, для каждого $P_{i}(x)$, множество всех кандидатов большинства $C_{i}(x)$ хранятся. Более конкретно, $C_{i}(x)$ содержит набор всех $(\tau /2)$-большинство в $P_{i}(x)$ или ярлыки, которые появляются более чем $(\tau /2).(2^{i}+1)$ раз в $P_{i}(x)$. Легко видеть, что множество кандидатов $C_{i}(x)$ может иметь максимум $2/\tau$ отдельные этикетки для каждого $i$. Гаги и др. то обратите внимание, что набор всех $\tau$-большинство на пути от любого отмеченного узла $x$ одному из своих предков $z$ входит в некоторые $C_{i}(x)$ (лемма 2 в ), так как длина $P_{i}(x)$ равно $(2^{i}+1)$ таким образом, существует $P_{i}(x)$ для $0\leq i\leq \log(depth(x))$ длина которого находится между $d_{xz}{\text{ and }}2d_{xz}$ где $d_{xz}$ расстояние между x и z. Существование таких $P_{i}(x)$ подразумевает, что $\tau$-большинство на пути от $x$ к $z$ должно быть $(\tau /2)$-большинство в $P_{i}(x)$, и поэтому должен появиться в $C_{i}(x)$. Легко видеть, что эта структура данных требует $O(n\log n)$ слова космоса, потому что как уже говорилось выше на этапе строительства $O(\tau n)$ узлы помечены, и для каждого помеченного узла сохраняются некоторые наборы кандидатов. По определению для каждого отмеченного узла $O(\log n)$ таких наборов являются магазинами, каждый из которых содержит $O(1/\tau )$ кандидаты. Следовательно, эта структура данных требует $O(\log n\times (1/\tau )\times \tau n)=O(n\log n)$ слова космоса. Обратите внимание, что каждый узел $x$ также магазины $count(x)$ что равно количеству экземпляров $label(x)$ по пути из $x$ в корень $T$, это не увеличивает сложность пространства, поскольку добавляет только постоянное количество слов на узел.

Каждый запрос между двумя узлами $u$ и $v$ можно ответить, используя свойство разложимости (как объяснено выше) диапазона $\tau$-большинство запросов и разрывая путь запроса между $u$ и $v$ на четыре подпути. Позволять $z$ быть низшим общим предком $u$ и $v$, с $x$ и $y$ являющихся ближайшими отмеченными предками $u$ и $v$ соответственно. Путь от $u$ к $v$ разлагается на пути из $u$ и $v$ к $x$ и $y$ соответственно (размер этих путей меньше, чем $2\lceil 1/\tau \rceil$ по определению все они рассматриваются как кандидаты), а пути от $x$ и $y$ к $z$ (путем нахождения подходящего $C_{i}(x)$ как объяснялось выше, и рассматривая все его ярлыки как кандидатов). Обратите внимание, что граничные узлы должны обрабатываться соответствующим образом, чтобы все эти подпути были непересекающимися и из всех них создавался набор $O(1/\tau )$ выводятся кандидаты. Каждый из этих кандидатов затем проверяется с использованием комбинации $labelanc(x,\ell )$ запрос, который возвращает наименьшего предка узла $x$ у которого есть этикетка $\ell$ и $count(x)$ поля каждого узла. На $w$-битная оперативная память и алфавит размера $\sigma$, $labelanc(x,\ell )$ на запрос можно ответить в $O\left(\log \log _{w}\sigma \right)$ времени при наличии требований к линейному пространству. Поэтому проверка каждого из $O(1/\tau )$ кандидатов в $O\left(\log \log _{w}\sigma \right)$ время приводит к $O\left((1/\tau )\log \log _{w}\sigma \right)$ общее время запроса для возврата набора всех $\tau$-большинство на пути от $u$ к $v$.

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

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

См. также

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

Внешние ссылки

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