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

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

Постановка задачи

Учитывая массив $A[1:n]=[a_{1},a_{2},...,a_{n}]$, мы хотим ответить на запросы вида $mode(A,i:j)$, где $1\leq i\leq j\leq n$. Режим $mode(S)$ любого массива $S=[s_{1},s_{2},...,s_{k}]$ это элемент $s_{i}$ такая, что частота $s_{i}$ больше или равна частоте $s_{j}\;\forall j\in \{1,...,k\}$. Например, если $S=[1,2,4,2,3,4,2]$, затем $mode(S)=2$ потому что оно встречается три раза, тогда как все остальные значения встречаются меньше раз. В этой задаче запросы запрашивают режим подмассивов вида $A[i:j]=[a_{i},a_{i+1},...,a_{j}]$.

Теорема 1

Позволять $A$ и $B$ быть любыми мультимножествами . Если $c$ это режим $A\cup B$ и $c\notin A$, затем $c$ это режим $B$.

Доказательство

Позволять $c\notin A$ быть способом $C=A\cup B$ и $f_{c}$ быть его частота в $C$. Предположим, что $c$ не является способом $B$. Таким образом, существует элемент $b$ с частотой $f_{b}$ это режим $B$. С $b$ это режим $B$ и это $c\notin A$, затем $f_{b}>f_{c}$. Таким образом, $b$ должен быть режим $C$ что является противоречием.

Результаты

Космос	Время запроса	Ограничения	Источник
$O(n)$	$O({\sqrt {n}})$
$O(n)$	$O({\sqrt {n/w}})$	$w$ размер слова
$O(n^{2}\log \log n/\log n)$	$O(1)$
$O(n^{2-2\epsilon }/\log n)$	$O(n^{\epsilon })$	$0\leq \epsilon \leq 1/2$
$O(n^{2-2\epsilon })$	$O(n^{\epsilon }\log n)$	$0\leq \epsilon \leq 1/2$

Нижняя граница

Любая структура данных, использующая $S$ клетки $w$ биты, которые нужны каждому $\Omega \left({\frac {\log n}{\log(Sw/n)}}\right)$ время для ответа на запрос режима диапазона.

Это контрастирует с другими проблемами запроса диапазона, такими как запрос минимального диапазона, решения которого предлагают постоянное время запроса и линейное пространство. Это связано со сложностью модовой задачи, поскольку даже если мы знаем моду $A[i:j]$ и режим $A[j+1:k]$, не существует простого способа вычисления режима $A[i:k]$. Любой элемент $A[i:j]$ или $A[j+1:k]$ может быть режим. Например, если $mode(A[i:j])=a$ и его частота $f_{a}$, и $mode(A[j+1:k])=b$ и его частота также $f_{a}$, может быть элемент $c$ с частотой $f_{a}-1$ в $A[i:j]$ и частота $f_{a}-1$ в $A[j+1:k]$. $a\not =c\not =b$, но его частота в $A[i:k]$ больше, чем частота $a$ и $b$, что делает $c$ лучший кандидат на $mode(A[i:k])$ чем $a$ или $b$.

Структура данных линейного пространства со временем запроса квадратного корня

Этот метод Chan et al. использует $O(n+s^{2})$ пространство и $O(n/s)$ время запроса. Установив $s={\sqrt {n}}$, мы получаем $O(n)$ и $O({\sqrt {n}})$ границы пространства и времени запроса.

Предварительная обработка

Позволять $A[1:n]$ быть массивом, и $D[1:\Delta ]$ быть массивом, содержащим различные значения A, где $\Delta$ количество различных элементов. Мы определяем $B[1:n]$ быть массивом таким, что для каждого $i$, $B[i]$ содержит ранг (должность) $A[i]$ в $D$. Массивы $B,D$ может быть создан путем линейного сканирования $A$.

Массивы $Q_{1},Q_{2},...,Q_{\Delta }$ создаются также такие, что для каждого $a\in \{1,...,\Delta \}$, $Q_{a}=\{b\;|\;B[b]=a\}$. Затем мы создаем массив $B'[1:n]$, такой, что для всех $b\in \{1,...,n\}$, $B'[b]$ содержит ранг $b$ в $Q_{B[b]}$. И снова линейное сканирование $B$ достаточно для создания массивов $Q_{1},Q_{2},...,Q_{\Delta }$ и $B'$.

Теперь можно отвечать на запросы вида «частота $B[i]$ в $B[i:j]$ по меньшей мере $q$" в постоянное время, проверяя, $Q_{B[i]}[B'[i]+q-1]\leq j$.

Массив разделен B на $s$ блоки $b_{1},b_{2},...,b_{s}$, каждый размера $t=\lceil n/s\rceil$. Таким образом, блок $b_{i}$ охватывает $B[i\cdot t+1:(i+1)t]$. Режим и частота каждого блока или набора последовательных блоков будут предварительно рассчитаны в двух таблицах. $S$ и $S'$. $S[b_{i},b_{j}]$ это режим $b_{i}\cup b_{i+1}\cup ...\cup b_{j}$или, что эквивалентно, режим $B[b_{i}t+1:(b_{j}+1)t]$, и $S'$ сохраняет соответствующую частоту. Эти две таблицы могут храниться в $O(s^{2})$ пространстве и может быть заселен в $O(s\cdot n)$ путем сканирования $B$ $s$ раз, вычисляя строку $S,S'$ каждый раз по следующему алгоритму:

algorithm computeS_Sprime is
    input: Array B = [0:n - 1], 
        Array D = [0:Delta - 1], 
        Integer s
    output: Tables S and Sprime
    let S ← Table(0:n - 1, 0:n - 1)
    let Sprime ← Table(0:n - 1, 0:n - 1)
    let firstOccurence ← Array(0:Delta - 1)
    for all i in {0, ..., Delta - 1} do
        firstOccurence[i] ← -1 
    end for
    for i ← 0:s - 1 do    
        let j ← i × t
        let c ← 0
        let fc ← 0
        let noBlock ← i
        let block_start ← j
        let block_end ← min{(i + 1) × t - 1, n - 1}
        while j < n do    
            if firstOccurence[B[j]] = -1 then
                firstOccurence[B[j]] ← j
            end if		
            if atLeastQInstances(firstOccurence[B[j]], block_end, fc + 1) then
                c ← B[j]
                fc ← fc + 1
            end if		
            if j = block_end then
                S[i * s + noBlock] ← c
                Sprime[i × s + noBlock] ← fc			
                noBlock ← noBlock + 1
                block_end ← min{block_end + t, n - 1}
            end if
        end while
        for all j in {0, ..., Delta - 1} do
            firstOccurence[j] ← -1 
        end for
    end for

Запрос

Мы определим алгоритм запроса по массиву $B$. Это можно перевести в ответ $A$, поскольку для любого $a,i,j$, $B[a]$ это режим для $B[i:j]$ тогда и только тогда, когда $A[a]$ это режим для $A[i:j]$. Мы можем преобразовать ответ для $B$ к ответу на $A$ в постоянное время, заглянув $A$ или $B$ по соответствующему индексу.

Учитывая запрос $mode(B,i,j)$, запрос разбивается на три части: префикс, диапазон и суффикс. Позволять $b_{i}=\lceil (i-1)/t\rceil$ и $b_{j}=\lfloor j/t\rfloor -1$. Они обозначают индексы первого и последнего блока, которые полностью содержатся в $B$. Диапазон этих блоков называется промежутком. Тогда префикс $B[i:min\{b_{i}t,j\}]$ (набор индексов перед диапазоном), а суффикс — $B[max\{(b_{j}+1)t+1,i\}:j]$ (набор индексов после промежутка). Префикс, суффикс или диапазон могут быть пустыми, последнее — если $b_{j}<b_{i}$.

Для пролета режим $c$ уже хранится в $S[b_{i},b_{j}]$. Позволять $f_{c}$ быть частотой моды, которая хранится в $S'[b_{i},b_{j}]$. Если диапазон пуст, пусть $f_{c}=0$. Напомним, что по теореме 1 мода $B[i:j]$ является либо элементом префикса, диапазона или суффикса. Линейное сканирование выполняется для каждого элемента в префиксе и суффиксе, чтобы проверить, превышает ли его частота текущий кандидат. $c$, в этом случае $c$ и $f_{c}$ обновляются до нового значения. В конце сканирования $c$ содержит режим $B[i:j]$ и $f_{c}$ его частота.

Процедура сканирования

Процедура аналогична как для префикса, так и для суффикса, поэтому достаточно запустить эту процедуру для обоих:

Позволять $x$ быть индексом текущего элемента. Есть три случая:

1. Если $Q_{B[x]}[B'[x]-1]\geq i$, тогда оно присутствовало в $B[i:x-1]$ и его частота уже подсчитана. Переход к следующему элементу.
2. В противном случае проверьте, если частота $B[x]$ в $B[i:j]$ по крайней мере $f_{c}$ (это можно сделать за постоянное время, поскольку это эквивалентно проверке на наличие $B[x:j]$).
   1. Если это не так, то переходим к следующему элементу.
   2. Если да, то вычислите фактическую частоту $f_{x}$ из $B[x]$ в $B[i:j]$ линейным сканированием (начиная с индекса $B'[x]+f_{c}-1$) или бинарный поиск в $Q_{B[x]}$. Набор $c:=B[x]$ и $f_{c}:=f_{x}$.

Это линейное сканирование (исключая вычисления частоты) ограничено размером блока. $t$, поскольку ни префикс, ни суффикс не могут быть больше, чем $t$. Дальнейший анализ линейных сканирований, выполненных для вычислений частоты, показывает, что они также ограничены размером блока. Таким образом, время запроса $O(t)=O(n/s)$.

Структура данных субквадратичного пространства с постоянным временем запроса

Этот метод по использует $O\left({\frac {n^{2}\log {\log {n}}}{\log {n}}}\right)$ пространство для запроса постоянного времени. Мы можем заметить, что если требуется постоянное время запроса, это лучшее решение, чем решение, предложенное Чаном и др.: поскольку последний дает пространство $O(n^{2})$ для постоянного времени запроса, если $s=n$.

Предварительная обработка

Позволять $A[1:n]$ быть массивом. Предварительная обработка выполняется в три этапа:

1. Разделить массив $A$ в $s$ блоки $b_{1},b_{2},...,b_{s}$, где размер каждого блока равен $t=\lceil n/s\rceil$. Построить стол $S$ размера $s\times s$ где $S[i,j]$ это режим $b_{i}\cup b_{i+1}\cup ...\cup b_{j}$. Общее пространство для этого шага составляет $O(s^{2})$
2. На любой запрос $mode(A,i,j)$, позволять $b_{i'}$ быть блоком, который содержит $i$ и $b_{j'}$ быть блоком, который содержит $j$. Пусть промежутком будет множество блоков, полностью содержащихся в $A[i:j]$. Режим $c$ блока можно получить из $S$. По теореме 1 модой может быть либо элемент префикса (индексы $A[i:j]$ перед началом промежутка), элемент суффикса (индексы $A[i:j]$ после окончания интервала), или $c$. Размер префикса плюс размер суффикса ограничен $2t$, таким образом, положение режима сохраняется как целое число в диапазоне от $0$ к $2t$, где $[0:2t-1]$указывает позицию в префиксе/суффиксе и $2t$ указывает, что режим является режимом диапазона. Есть ${\binom {t}{2}}$ возможные запросы с участием блоков $b_{i'}$ и $b_{j'}$, поэтому эти значения сохраняются в таблице размера $t^{2}$. Кроме того, существуют $(2t+1)^{t^{2}}$ такие таблицы, поэтому общее пространство, необходимое для этого шага, равно $O(t^{2}(2t+1)^{t^{2}})$. Для доступа к этим таблицам в дополнение к режиму в таблице добавляется указатель. $S$ для каждой пары блоков.
3. Для обработки запросов $mode(A,i,j)$ где $i$ и $j$ находятся в одном блоке, все такие решения вычисляются заранее. Есть $O(st^{2})$ из них они хранятся в трехмерной таблице $T$ такого размера.

Общий объем пространства, используемого этой структурой данных, равен $O(s^{2}+t^{2}(2t+1)^{t^{2}}+st^{2})$, что сводится к $O\left({\frac {n^{2}\log {\log {n}}}{\log {n}}}\right)$ если мы возьмем $t={\sqrt {\log {n}/\log {\log {n}}}}$.

Запрос

Учитывая запрос $mode(A,i,j)$, проверьте, полностью ли он содержится внутри блока, и в этом случае ответ сохраняется в таблице $T$. Если запрос охватывает ровно один или несколько блоков, то ответ находится в таблице $S$. В противном случае используйте указатель, хранящийся в таблице $S$ на позиции $S[b_{i'},b_{j'}]$, где $b_{i'},b_{j'}$ — индексы блоков, содержащих соответственно $i$ и $j$, чтобы найти таблицу $U_{b_{i'},b_{j'}}$ который содержит позиции режима для этих блоков и использует эту позицию для поиска режима в $A$. Это можно сделать за постоянное время.