Hispanopedia Wiki
Articulo de referencia

Consulta de rango (informática)

En informática , el problema de consulta de rango consiste en responder de manera eficiente a varias consultas sobre un intervalo de elementos dentro de un arreglo . Por ejemplo...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el problema de consulta de rango consiste en responder de manera eficiente a varias consultas sobre un intervalo de elementos dentro de un arreglo . Por ejemplo, una tarea común, conocida como consulta de mínimo de rango , consiste en encontrar el valor más pequeño dentro de un rango dado en una lista de números.

Definición

Dada una funciónF{\displaystyle f}que acepta una matriz, una consulta de rangoFq(l,r){\displaystyle f_{q}(l,r)}en una matriza=[a1,..,anorte]{\displaystyle a=[a_{1},..,a_{n}]}toma dos índicesl{\displaystyle l}yr{\displaystyle r}y devuelve el resultado deF{\displaystyle f}cuando se aplica al subconjunto[al,…,ar]{\displaystyle [a_{l},\ldots ,a_{r}]}. Por ejemplo, para una funciónsuma{\displaystyle \operatorname {sum} }que devuelve la suma de todos los valores en una matriz, la consulta de rangosumaq⁡(l,r){\displaystyle \operatorname {sum} _{q}(l,r)}devuelve la suma de todos los valores en el rango[l,r]{\displaystyle [l,r]}.

Soluciones

Matriz de suma de prefijos

Las consultas de suma de rangos pueden responderse en tiempo constante y espacio lineal precalculando una matriz p de la misma longitud que la entrada, de modo que para cada índice i , el elemento p i sea la suma de los primeros i elementos de a . Cualquier consulta puede calcularse entonces de la siguiente manera:sumaq⁡(l,r)=pagr−pagl−1.{\displaystyle \operatorname {sum} _{q}(l,r)=p_{r}-p_{l-1}.}

Esta estrategia puede extenderse a cualquier otra operación binaria.F{\displaystyle f}cuya función inversaF−1{\displaystyle f^{-1}}está bien definido y es fácilmente computable. [ 1 ] También puede extenderse a dimensiones superiores con un preprocesamiento similar. [ 2 ] Por ejemplo, si p i,j contiene la suma de los primeros i × j elementos de a , entoncessumaq⁡(l,r,t,b)=pagr,b−pagl−1,b−pagr,t−1+pagl−1,t−1.{\displaystyle \operatorname {sum} _{q}(l,r,t,b)=p_{r,b}-p_{l-1,b}-p_{r,t-1}+p_{l-1,t-1}.}

Consultas de rango dinámico

Un subconjunto más complejo del problema consiste en ejecutar consultas de rango sobre datos dinámicos; es decir, datos que pueden modificarse entre cada consulta. Para actualizar eficientemente los valores de los arrays, se requieren estructuras de datos más sofisticadas, como el árbol de segmentos o el árbol de Fenwick .

Ejemplos

Operadores de semigrupo

Construir el árbol cartesiano correspondiente para resolver una consulta de mínimo de rango.
La consulta de rango mínimo se reduce al problema del ancestro común más bajo .

Cuando la función de interés en una consulta de rango es un operador de semigrupo , la noción deF−1{\displaystyle f^{-1}}no siempre está definido, por lo que la estrategia de la sección anterior no funciona. Andrew Yao demostró [ 3 ] que existe una solución eficiente para consultas de rango que involucran operadores de semigrupo. Demostró que para cualquier constante c , un preprocesamiento de tiempo y espacioΘ(do⋅norte){\displaystyle \Theta (c\cdot n)}permite responder consultas de rango en listas donde f es un operador de semigrupo enθ(αdo(norte)){\displaystyle \theta (\alpha _{c}(n))}tiempo, dondeαdo{\displaystyle \alpha _{c}}es una cierta inversa funcional de la función de Ackermann .

Hay algunos operadores de semigrupo que admiten soluciones ligeramente mejores. Por ejemplo, cuandoF∈{máximo,min}{\displaystyle f\in \{\max ,\min \}}. AsumirF=min{\displaystyle f=\min }entoncesmin(A[1..norte]){\displaystyle \min(A[1..n])}devuelve el índice del elemento mínimo deA[1..norte]{\displaystyle A[1..n]}. Entoncesmini,j(A){\textstyle \min _{i,j}(A)}denota la consulta de rango mínimo correspondiente. Existen varias estructuras de datos que permiten responder a una consulta de rango mínimo enO(1){\displaystyle O(1)}tiempo utilizando un preprocesamiento de tiempo y espacioO(norte){\displaystyle O(n)}Una de esas soluciones se basa en la equivalencia entre este problema y el problema del ancestro común más bajo .

El árbol cartesianoTA{\displaystyle T_{A}}de una matrizA[1,norte]{\displaystyle A[1,n]}tiene como raízai=min{a1,a2,…,anorte}{\displaystyle a_{i}=\min\{a_{1},a_{2},\ldots ,a_{n}\}}y como subárboles izquierdo y derecho el árbol cartesiano deA[1,i−1]{\displaystyle A[1,i-1]}y el árbol cartesiano deA[i+1,norte]{\displaystyle A[i+1,n]}respectivamente. Una consulta de rango mínimomini,j(A){\textstyle \min _{i,j}(A)}es el ancestro común más bajo enTA{\displaystyle T_{A}}deai{\displaystyle a_{i}}yaj{\displaystyle a_{j}}. Porque el ancestro común más bajo se puede resolver en tiempo constante utilizando un preprocesamiento de tiempo y espacio.O(norte){\displaystyle O(n)}, la consulta de rango mínimo también puede. La solución cuandoF=máximo{\displaystyle f=\max }es análogo. Los árboles cartesianos se pueden construir en tiempo lineal .

Modo

La moda de un array es el elemento que aparece con mayor frecuencia en él. Por ejemplo, la moda dea=[4,5,6,7,4]{\displaystyle a=[4,5,6,7,4]}es4. En caso de empate, cualquiera de los elementos más frecuentes podría ser elegido como la moda. Una consulta de modo de rango consiste en un preprocesamientoA[1,norte]{\displaystyle A[1,n]}de tal manera que podamos encontrar la moda en cualquier rango deA[1,norte]{\displaystyle A[1,n]}Se han ideado varias estructuras de datos para resolver este problema; resumimos algunos de los resultados en la siguiente tabla. [ 1 ]

Recientemente, Jørgensen et al. demostraron un límite inferior en el modelo de sonda celular deΩ(registro⁡norteregistro⁡(Sw/norte)){\displaystyle \Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)}para cualquier estructura de datos que utilice celdas S. [ 4 ]

Mediana

Este caso particular es de especial interés ya que encontrar la mediana tiene varias aplicaciones. [ 5 ] Por otro lado, el problema de la mediana, un caso especial del problema de selección , es resoluble en O ( n ), utilizando el algoritmo de la mediana de medianas . [ 6 ] Sin embargo, su generalización a través de consultas de mediana de rango es reciente. [ 7 ] Una consulta de mediana de rangomediana⁡(A,i,j){\displaystyle \operatorname {median} (A,i,j)}donde A, i y j tienen los significados habituales devuelve el elemento mediano deA[i,j]{\displaystyle A[i,j]}. De forma equivalente,mediana⁡(A,i,j){\displaystyle \operatorname {median} (A,i,j)}debería devolver el elemento deA[i,j]{\displaystyle A[i,j]}de rangoj−i2{\displaystyle {\frac {ji}{2}}}Las consultas de mediana de rango no se pueden resolver siguiendo ninguno de los métodos anteriores discutidos anteriormente, incluido el enfoque de Yao para operadores de semigrupo. [ 8 ]

Se han estudiado dos variantes de este problema: la versión fuera de línea , donde todas las k consultas de interés se proporcionan en un lote, y una versión donde todo el preprocesamiento se realiza por adelantado. La versión fuera de línea se puede resolver conO(norteregistro⁡k+kregistro⁡norte){\displaystyle O(n\log k+k\log n)}tiempo yO(norteregistro⁡k){\displaystyle O(n\log k)}espacio.

El siguiente pseudocódigo del algoritmo quickselect muestra cómo encontrar el elemento de rango r enA[i,j]{\displaystyle A[i,j]}una matriz no ordenada de elementos distintos, para encontrar las medianas de rango que establecemosr=j−i2{\displaystyle r={\frac {ji}{2}}}. [ 7 ]

rangoMediana(A, i, j, r) { si A.length() == 1, devolver A[1] Si A.low no está definido, entonces m = mediana(A) A.bajo = [e en A | e <= m] A.alto = [e en A | e > m ] Calcula el número de elementos de A[i, j] que pertenecen a A.low Si r <= t, entonces devuelve rangeMedian(A.low, i, j, r); de lo contrario, devuelve rangeMedian(A.high, i, j, rt). }

El procedimiento rangeMediandivide A, usando Ala mediana de , en dos arreglos A.lowy A.high, donde el primero contiene los elementos de Aque son menores o iguales a la mediana my el segundo el resto de los elementos de A. Si sabemos que el número de elementos deA[i,j]{\displaystyle A[i,j]}que terminan en A.lowes ty este número es mayor que rentonces deberíamos seguir buscando el elemento de rango ren A.low; de lo contrario deberíamos buscar el elemento de rango(r−t){\displaystyle (rt)}en A.high. Para encontrar t , basta con encontrar el índice máximo.metro≤i−1{\displaystyle m\leq i-1}de tal manera queametro{\displaystyle a_{m}}está en A.lowy el índice máximol≤j{\displaystyle l\leq j}de tal manera queal{\displaystyle a_{l}} está en A.high. Entoncest=l−metro{\displaystyle t=lm}El costo total de cualquier consulta, sin considerar la parte de particionamiento, esregistro⁡norte{\displaystyle \log n}ya que como máximoregistro⁡norte{\displaystyle \log n}Las llamadas recursivas se realizan y solo se lleva a cabo un número constante de operaciones en cada una de ellas (para obtener el valor de t se debe utilizar la cascada fraccionaria ). Si se utiliza un algoritmo lineal para encontrar las medianas, el costo total del preprocesamiento para k consultas de mediana de rango esnorteregistro⁡k{\displaystyle n\log k}. El algoritmo también puede modificarse para resolver la versión en línea del problema. [ 7 ]

Mayoría

Encontrar elementos frecuentes en un conjunto dado de elementos es una de las tareas más importantes en la minería de datos. Encontrar elementos frecuentes puede ser una tarea difícil de lograr cuando la mayoría de los elementos tienen frecuencias similares. Por lo tanto, podría ser más beneficioso si se utilizara algún umbral de significancia para detectar dichos elementos. Uno de los algoritmos más famosos para encontrar la mayoría de un arreglo fue propuesto por Boyer y Moore [ 9 ] , también conocido como el algoritmo de votación mayoritaria de Boyer-Moore . Boyer y Moore propusieron un algoritmo para encontrar el elemento mayoritario de una cadena (si tiene uno) enO(norte){\displaystyle O(n)}tiempo y uso O(1){\displaystyle O(1)}espacio. En el contexto del trabajo de Boyer y Moore y en términos generales, un elemento mayoritario en un conjunto de elementos (por ejemplo, una cadena o una matriz) es aquel cuyo número de instancias es más de la mitad del tamaño de ese conjunto. Unos años más tarde, Misra y Gries [ 10 ] propusieron una versión más general del algoritmo de Boyer y Moore utilizandoO(norteregistro⁡(1τ)){\displaystyle O\left(n\log \left({\frac {1}{\tau }}\right)\right)}comparaciones para encontrar todos los elementos en una matriz cuyas frecuencias relativas sean mayores que un cierto umbral.0<τ<1{\displaystyle 0<\tau <1}. Una gamaτ{\displaystyle \tau }-La consulta mayoritaria es aquella que, dado un subrango de una estructura de datos (por ejemplo, una matriz) de tamaño|R|{\displaystyle |R|}, devuelve el conjunto de todos los elementos distintos que aparecen más que (o en algunas publicaciones igual a)τ|R|{\displaystyle \tau |R|}veces en ese rango dado. En diferentes estructuras que admiten rangoτ{\displaystyle \tau }-consultas mayoritarias,τ{\displaystyle \tau }puede ser estático (especificado durante el preprocesamiento) o dinámico (especificado en el momento de la consulta). Muchos de estos enfoques se basan en el hecho de que, independientemente del tamaño del rango, para un dadoτ{\displaystyle \tau }podría haber como máximoO(1/τ){\displaystyle O(1/\tau )}candidatos distintos con frecuencias relativas al menosτ{\displaystyle \tau }. Al verificar cada uno de estos candidatos en tiempo constante, O(1/τ){\displaystyle O(1/\tau )}Se logra el tiempo de consulta. Un rangoτ{\displaystyle \tau }-la consulta de mayoría es descomponible [ 11 ] en el sentido de que unaτ{\displaystyle \tau }-mayoría en un rangoR{\displaystyle R}con particionesR1{\displaystyle R_{1}}yR2{\displaystyle R_{2}}debe ser unτ{\displaystyle \tau }-mayoría en cualquiera de los dosR1{\displaystyle R_{1}}oR2{\displaystyle R_{2}}Debido a esta descomponibilidad, algunas estructuras de datos respondenτ{\displaystyle \tau }-Consultas de mayoría en matrices unidimensionales mediante la búsqueda del ancestro común más bajo (LCA) de los puntos finales del rango de consulta en un árbol de rango y la validación de dos conjuntos de candidatos (de tamañoO(1/τ){\displaystyle O(1/\tau )}) desde cada punto final hasta el ancestro común más bajo en tiempo constante, lo que resulta enO(1/τ){\displaystyle O(1/\tau )}tiempo de consulta.

Matrices bidimensionales

Gagie et al. [ 12 ] propusieron una estructura de datos que admite rangoτ{\displaystyle \tau }-mayoría de consultas en un metro×norte{\displaystyle m\times n}formaciónA{\displaystyle A}. Para cada consultaQ=(R,τ){\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}en esta estructura de datos un umbral0<τ<1{\displaystyle 0<\tau <1}y un rango rectangularR{\displaystyle \operatorname {R} }se especifican, y el conjunto de todos los elementos que tienen frecuencias relativas (dentro de ese rango rectangular) mayores o iguales aτ{\displaystyle \tau }se devuelven como resultado. Esta estructura de datos admite umbrales dinámicos (especificados en el momento de la consulta) y un umbral de preprocesamiento.α{\displaystyle \alpha }sobre la cual se construye. Durante el preprocesamiento, se construye un conjunto de intervalos verticales y horizontales sobre la base demetro×norte{\displaystyle m\times n}matriz. Juntos, un intervalo vertical y uno horizontal forman un bloque. Cada bloque es parte de un superbloque nueve veces más grande que él mismo (tres veces el tamaño del intervalo horizontal del bloque y tres veces el tamaño del vertical). Para cada bloque, un conjunto de candidatos (con9α{\displaystyle {\frac {9}{\alpha }}}elementos como máximo) se almacena que consiste en elementos que tienen frecuencias relativas al menosα9{\displaystyle {\frac {\alpha }{9}}}(el umbral de preprocesamiento mencionado anteriormente) en su respectivo superbloque. Estos elementos se almacenan en orden no creciente según sus frecuencias y es fácil ver que cualquier elemento que tenga una frecuencia relativa al menosα{\displaystyle \alpha }En un bloque debe aparecer su conjunto de candidatos. Cadaτ{\displaystyle \tau }-La consulta mayoritaria se responde primero encontrando el bloque de consulta, o el bloque más grande que está contenido en el rectángulo de consulta proporcionado enO(1){\displaystyle O(1)}tiempo. Para el bloque de consulta obtenido, el primero9τ{\displaystyle {\frac {9}{\tau }}}Los candidatos son devueltos (sin ser verificados) enO(1/τ){\displaystyle O(1/\tau )}tiempo, por lo que este proceso podría devolver algunos falsos positivos. Muchas otras estructuras de datos (como se analiza a continuación) han propuesto métodos para verificar cada candidato en tiempo constante y, por lo tanto, mantener elO(1/τ){\displaystyle O(1/\tau )}tiempo de consulta sin devolver falsos positivos. Los casos en los que el bloque de consulta es menor que1/α{\displaystyle 1/\alpha }se manejan almacenandoregistro⁡(1α){\displaystyle \log \left({\frac {1}{\alpha }}\right)}diferentes instancias de esta estructura de datos de la siguiente forma:

β=2−i,i∈{1,…,registro⁡(1α)}{\displaystyle \beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}}

dóndeβ{\displaystyle \beta }es el umbral de preprocesamiento de lai{\displaystyle i}-ésima instancia. Por lo tanto, para bloques de consulta más pequeños que1/α{\displaystyle 1/\alpha }el⌈registro⁡(1/τ)⌉{\displaystyle \lceil \log(1/\tau )\rceil }Se consulta la instancia -ésima. Como se mencionó anteriormente, esta estructura de datos tiene tiempo de consulta. O(1/τ){\displaystyle O(1/\tau )}y requiereO(metronorte(H+1)registro2⁡(1α)){\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}bits de espacio almacenando una copia codificada de Huffman (tenga en cuenta elregistro⁡(1α){\displaystyle \log({\frac {1}{\alpha }})}factor y también ver codificación de Huffman ).

Matrices unidimensionales

Chan et al. [ 13 ] propusieron una estructura de datos que, dado un arreglo unidimensional,A{\displaystyle A}, una subrangoR{\displaystyle R}deA{\displaystyle A}(especificado en el momento de la consulta) y un umbralτ{\displaystyle \tau }(especificado en el momento de la consulta), es capaz de devolver la lista de todosτ{\displaystyle \tau }-mayorías enO(1/τ){\displaystyle O(1/\tau )}tiempo requeridoO(norteregistro⁡norte){\displaystyle O(n\log n)}palabras de espacio. Para responder a tales consultas, Chan et al. [ 13 ] comienzan señalando que existe una estructura de datos capaz de devolver los k elementos más frecuentes en un rango enO(k){\displaystyle O(k)}tiempo requeridoO(norte){\displaystyle O(n)}palabras de espacio. Para una matriz unidimensionalA[0,..,norte−1]{\displaystyle A[0,..,n-1]}, sea una consulta de rango top-k unilateral de la formaA[0..i] para 0≤i≤norte−1{\displaystyle A[0..i]{\text{ para }}0\leq i\leq n-1}. Para un rango máximo de rangosA[0..i] a través de A[0..j]{\displaystyle A[0..i]{\text{ a través de }}A[0..j]}en la que la frecuencia de un elemento distintomi{\displaystyle e}enA{\displaystyle A}permanece sin cambios (y es igual aF{\displaystyle f}), se construye un segmento de línea horizontal. Elincógnita{\displaystyle x}-el intervalo de este segmento de línea corresponde a[i,j]{\displaystyle [i,j]}y tiene uny{\displaystyle y}-valor igual aF{\displaystyle f}. Desde que se agrega cada elemento aA{\displaystyle A}cambia la frecuencia de exactamente un elemento distinto, el proceso mencionado anteriormente creaO(norte){\displaystyle O(n)}segmentos de línea. Además, para una línea verticalincógnita=i{\displaystyle x=i}Todos los segmentos de línea horizontales que la intersecan se ordenan según sus frecuencias. Tenga en cuenta que cada segmento de línea horizontal conincógnita{\displaystyle x}-intervalo[ℓ,r]{\displaystyle [\ell ,r]}corresponde exactamente a un elemento distintomi{\displaystyle e}enA{\displaystyle A}, de tal manera queA[ℓ]=mi{\displaystyle A[\ell ]=e}Una consulta top-k puede responderse entonces disparando un rayo vertical.incógnita=i{\displaystyle x=i}y reportando el primerok{\displaystyle k}segmentos de línea horizontales que la intersecan (recuerde de arriba que estos segmentos de línea ya están ordenados según sus frecuencias) enO(k){\displaystyle O(k)}tiempo.

Chan et al. [ 13 ] primero construyen un árbol de rango en el que cada nodo de ramificación almacena una copia de la estructura de datos descrita anteriormente para consultas top-k de rango unilateral y cada hoja representa un elemento deA{\displaystyle A}La estructura de datos top-k en cada nodo se construye en función de los valores existentes en los subárboles de ese nodo y está diseñada para responder a consultas top-k de rango unilateral. Tenga en cuenta que para una matriz unidimensionalA{\displaystyle A}, se puede construir un árbol de rangos dividiendoA{\displaystyle A}en dos mitades y recursivamente en ambas mitades; por lo tanto, cada nodo del árbol de rangos resultante representa un rango. También se puede observar que este árbol de rangos requiereO(norteregistro⁡norte){\displaystyle O(n\log n)}palabras de espacio, porque hayO(registro⁡norte){\displaystyle O(\log n)}niveles y cada nivelℓ{\displaystyle \ell }tiene2ℓ{\displaystyle 2^{\ell }}nodos. Además, puesto que en cada nivelℓ{\displaystyle \ell }de un árbol de rango todos los nodos tienen un total denorte{\displaystyle n}elementos deA{\displaystyle A}en sus subárboles y puesto que hayO(registro⁡norte){\displaystyle O(\log n)}niveles, la complejidad espacial de este árbol de rango esO(norteregistro⁡norte){\displaystyle O(n\log n)}.

Utilizando esta estructura, una gamaτ{\displaystyle \tau }-consulta mayoritariaA[i..j]{\displaystyle A[i..j]}enA[0..norte−1]{\displaystyle A[0..n-1]}con0≤i≤j≤norte{\displaystyle 0\leq i\leq j\leq n}se responde de la siguiente manera. Primero, el ancestro común más bajo (LCA) de los nodos hojai{\displaystyle i}yj{\displaystyle j}se encuentra en tiempo constante. Tenga en cuenta que existe una estructura de datos que requiereO(norte){\displaystyle O(n)}bits de espacio que son capaces de responder a las consultas LCA enO(1){\displaystyle O(1)}tiempo. [ 14 ] Dejez{\displaystyle z}denotamos el ACV dei{\displaystyle i}yj{\displaystyle j}, usandoz{\displaystyle z}y según la descomponibilidad del rangoτ{\displaystyle \tau }-consultas de mayoría (como se describe anteriormente y en [ 11 ] ), la consulta de rango bilateralA[i..j]{\displaystyle A[i..j]}se puede convertir en dos consultas top-k de rango unilateral (desdez{\displaystyle z}ai{\displaystyle i}yj{\displaystyle j}). Estas dos consultas de rango unilateral top-k devuelven los top-(1/τ{\displaystyle 1/\tau }) elementos más frecuentes en cada uno de sus respectivos rangos enO(1/τ){\displaystyle O(1/\tau )}tiempo. Estos elementos frecuentes conforman el conjunto de candidatos paraτ{\displaystyle \tau }-mayorías enA[i..j]{\displaystyle A[i..j]}en los que hayO(1/τ){\displaystyle O(1/\tau )}candidatos algunos de los cuales podrían ser falsos positivos. Cada candidato se evalúa luego en tiempo constante utilizando una estructura de datos de espacio lineal (como se describe en el Lema 3 en [ 15 ] ) que es capaz de determinar en O(1){\displaystyle O(1)}tiempo si un subrango dado de una matrizA{\displaystyle A}contiene al menosq{\displaystyle q}instancias de un elemento en particularmi{\displaystyle e}.

senderos arbolados

Gagie et al. [ 16 ] propusieron una estructura de datos que admite consultas tales que, dados dos nodostú{\displaystyle u}yv{\displaystyle v}en un árbol, pueden informar la lista de elementos que tienen una frecuencia relativa mayor queτ{\displaystyle \tau }en el camino desdetú{\displaystyle u}av{\displaystyle v}. Más formalmente, dejemosT{\displaystyle T}sea ​​un árbol etiquetado en el que cada nodo tiene una etiqueta de un alfabeto de tamañoσ{\displaystyle \sigma }. Dejarlabmil(tú)∈[1,…,σ]{\displaystyle label(u)\in [1,\dots ,\sigma ]}denota la etiqueta del nodotú{\displaystyle u}enT{\displaystyle T}. DejarPAGtúv{\displaystyle P_{uv}}denota el camino único desdetú{\displaystyle u}av{\displaystyle v}enT{\displaystyle T}en el que los nodos intermedios se enumeran en el orden en que se visitan. DadoT{\displaystyle T}y un umbral fijo (especificado durante el preprocesamiento)0<τ<1{\displaystyle 0<\tau <1}, una consultaQ(tú,v){\displaystyle Q(u,v)}debe devolver el conjunto de todas las etiquetas que aparecen más de τ|PAGtúv|{\displaystyle \tau |P_{uv}|}tiempos enPAGtúv{\displaystyle P_{uv}}.

Para construir esta estructura de datos, primeroO(τnorte){\displaystyle {O}(\tau n)}Los nodos están marcados . Esto se puede hacer marcando cualquier nodo que tenga una distancia al menos⌈1/τ⌉{\displaystyle \lceil 1/\tau \rceil }desde la parte inferior de los tres (altura) y cuya profundidad es divisible por⌈1/τ⌉{\displaystyle \lceil 1/\tau \rceil }Después de hacer esto, se puede observar que la distancia entre cada nodo y su ancestro marcado más cercano es menor que2⌈1/τ⌉{\displaystyle 2\lceil 1/\tau \rceil }. Para un nodo marcadoincógnita{\displaystyle x},registro⁡(dmipagth(incógnita)){\displaystyle \log(depth(x))}diferentes secuencias (caminos hacia la raíz)PAGi(incógnita){\displaystyle P_{i}(x)}se almacenan,

PAGi(incógnita)=⟨etiqueta⁡(incógnita),par⁡(incógnita),par2⁡(incógnita),…,par2i⁡(incógnita)⟩{\displaystyle P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle }

para0≤i≤registro⁡(dmipagth(incógnita)){\displaystyle 0\leq i\leq \log(depth(x))}dóndepar⁡(incógnita){\displaystyle \operatorname {par} (x)}devuelve la etiqueta del padre directo del nodoincógnita{\displaystyle x}Dicho de otro modo, para cada nodo marcado, se almacena el conjunto de todos los caminos con una longitud que sea potencia de dos (más uno para el propio nodo) hacia la raíz. Además, para cadaPAGi(incógnita){\displaystyle P_{i}(x)}, el conjunto de todos los candidatos mayoritariosdoi(incógnita){\displaystyle C_{i}(x)}se almacenan. Más específicamente,doi(incógnita){\displaystyle C_{i}(x)}contiene el conjunto de todos(τ/2){\displaystyle (\tau /2)}-mayorías enPAGi(incógnita){\displaystyle P_{i}(x)}o etiquetas que aparecen más de(τ/2).(2i+1){\displaystyle (\tau /2).(2^{i}+1)}tiempos enPAGi(incógnita){\displaystyle P_{i}(x)}Es fácil ver que el conjunto de candidatosdoi(incógnita){\displaystyle C_{i}(x)}puede tener como máximo2/τ{\displaystyle 2/\tau }etiquetas distintas para cadai{\displaystyle i}. Gagie et al. [ 16 ] luego señalan que el conjunto de todosτ{\displaystyle \tau }-mayorías en la ruta desde cualquier nodo marcadoincógnita{\displaystyle x}a uno de sus antepasadosz{\displaystyle z}está incluido en algunosdoi(incógnita){\displaystyle C_{i}(x)}(Lema 2 en [ 16 ] ) ya que la longitud dePAGi(incógnita){\displaystyle P_{i}(x)}es igual a(2i+1){\displaystyle (2^{i}+1)}por lo tanto existe unPAGi(incógnita){\displaystyle P_{i}(x)}para0≤i≤registro⁡(dmipagth(incógnita)){\displaystyle 0\leq i\leq \log(depth(x))}cuya longitud es entredincógnitaz y 2dincógnitaz{\displaystyle d_{xz}{\text{ and }}2d_{xz}}dóndedincógnitaz{\displaystyle d_{xz}}es la distancia entre x y z. La existencia de talPAGi(incógnita){\displaystyle P_{i}(x)}implica que unτ{\displaystyle \tau }-mayoría en el camino desdeincógnita{\displaystyle x}az{\displaystyle z}debe ser un(τ/2){\displaystyle (\tau /2)}-mayoría enPAGi(incógnita){\displaystyle P_{i}(x)}y por lo tanto debe aparecer endoi(incógnita){\displaystyle C_{i}(x)}Es fácil ver que esta estructura de datos requiereO(norteregistro⁡norte){\displaystyle O(n\log n)}palabras de espacio, porque como se mencionó anteriormente en la fase de construcciónO(τnorte){\displaystyle O(\tau n)}Los nodos están marcados y para cada nodo marcado se almacenan algunos conjuntos candidatos. Por definición, para cada nodo marcadoO(registro⁡norte){\displaystyle O(\log n)}de tales conjuntos son almacenes, cada uno de los cuales contieneO(1/τ){\displaystyle O(1/\tau )}candidatos. Por lo tanto, esta estructura de datos requiereO(registro⁡norte×(1/τ)×τnorte)=O(norteregistro⁡norte){\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}palabras de espacio. Tenga en cuenta que cada nodoincógnita{\displaystyle x}también tiendasdootúnortet(incógnita){\displaystyle count(x)}que es igual al número de instancias delabmil(incógnita){\displaystyle label(x)}en el camino desdeincógnita{\displaystyle x}a la raíz deT{\displaystyle T}Esto no aumenta la complejidad espacial, ya que solo agrega un número constante de palabras por nodo.

Cada consulta entre dos nodostú{\displaystyle u}yv{\displaystyle v}puede responderse utilizando la propiedad de descomponibilidad (como se explicó anteriormente) de rangoτ{\displaystyle \tau }-consultas mayoritarias y rompiendo la ruta de consulta entretú{\displaystyle u}yv{\displaystyle v}en cuatro subrutas. Dejez{\displaystyle z}ser el ancestro común más bajo detú{\displaystyle u}yv{\displaystyle v}, conincógnita{\displaystyle x}yy{\displaystyle y}siendo los antepasados ​​marcados más cercanos detú{\displaystyle u}yv{\displaystyle v}respectivamente. El camino desdetú{\displaystyle u}av{\displaystyle v}se descompone en los caminos desdetú{\displaystyle u}yv{\displaystyle v}aincógnita{\displaystyle x}yy{\displaystyle y}respectivamente (el tamaño de estos caminos es menor que2⌈1/τ⌉{\displaystyle 2\lceil 1/\tau \rceil }por definición, todos los cuales se consideran candidatos), y los caminos desdeincógnita{\displaystyle x}yy{\displaystyle y}az{\displaystyle z}(al encontrar el adecuado)doi(incógnita){\displaystyle C_{i}(x)}como se explicó anteriormente y considerando todas sus etiquetas como candidatas). Tenga en cuenta que los nodos límite deben manejarse de manera adecuada para que todos estos subcaminos sean disjuntos y de todos ellos se pueda obtener un conjunto deO(1/τ){\displaystyle O(1/\tau )}Se derivan los candidatos. Luego, cada uno de estos candidatos se verifica utilizando una combinación de loslabmilanortedo(incógnita,ℓ){\displaystyle labelanc(x,\ell )}consulta que devuelve el ancestro más bajo del nodoincógnita{\displaystyle x}que tiene etiquetaℓ{\displaystyle \ell }y eldootúnortet(incógnita){\displaystyle count(x)}campos de cada nodo. En unw{\displaystyle w}-bit RAM y un alfabeto de tamañoσ{\displaystyle \sigma }, ellabmilanortedo(incógnita,ℓ){\displaystyle labelanc(x,\ell )}La consulta puede ser respondida enO(registro⁡registrow⁡σ){\displaystyle O\left(\log \log _{w}\sigma \right)}tiempo mientras que se tienen requisitos de espacio lineales. [ 17 ] Por lo tanto, verificar cada uno de losO(1/τ){\displaystyle O(1/\tau )}candidatos enO(registro⁡registrow⁡σ){\displaystyle O\left(\log \log _{w}\sigma \right)}el tiempo resulta enO((1/τ)registro⁡registrow⁡σ){\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}tiempo total de consulta para devolver el conjunto de todosτ{\displaystyle \tau }-mayorías en el camino desdetú{\displaystyle u}av{\displaystyle v}.

Todos los problemas descritos anteriormente se han estudiado para dimensiones superiores, así como sus versiones dinámicas. Por otro lado, las consultas de rango podrían extenderse a otras estructuras de datos como árboles , [ 8 ] como el problema del ancestro de nivel . Una familia similar de problemas son las consultas de rango ortogonales , también conocidas como consultas de conteo.

Véase también

Referencias

  1. 1 2 Krizanc, Danny; Morin, Pat ; Smid, Michiel HM (2003). "Consultas de rango de modo y rango de mediana en listas y árboles" . ISAAC : 517–526 . arXiv : cs/0307034 . Bibcode : 2003cs........7034K .
  2. ↑ Meng, He; Munro, J. Ian; Nicholson, Patrick K. (2011). "Selección de rango dinámico en espacio lineal". ISAAC : 160–169 . arXiv : 1106.5076 .
  3. ↑ Yao, Andrew C. (1982). "Compensación espacio-temporal para responder consultas de rango (Resumen extendido)". Actas del decimocuarto simposio anual de la ACM sobre Teoría de la Computación - STOC '82 . págs. 128–136 . doi : 10.1145/800070.802185 . ISBN  0-89791-070-2.
  4. ^ Greve, Marcos; Jørgensen, Allan Grønlund; Larsen, Kasper Dalgaard; Truelsen, Jakob (2010). "Límites inferiores de la sonda celular y aproximaciones para el modo de rango". Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 6198. págs. 605– 616. doi : 10.1007/978-3-642-14165-2_51 . ISBN   978-3-642-14164-5.
  5. ^ Har-Peled, Sariel; Muthukrishnan, S. (2008). "Medianas de rango". Algoritmos - ESA 2008 . Apuntes de conferencias sobre informática. vol. 5193. págs. 503– 514. arXiv : 0807.0222 . doi : 10.1007/978-3-540-87744-8_42 . ISBN   978-3-540-87743-1.
  6. ↑ Blum, M. ; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (agosto de 1973). "Límites de tiempo para la selección" (PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 .
  7. 1 2 3 Gfeller, Beat; Sanders, Peter (2009). "Hacia medianas de rango óptimas". Autómatas, lenguajes y programación . Notas de clase en ciencias de la computación. Vol. 5555. págs. 475–486 . arXiv : 0901.1761 . doi : 10.1007/978-3-642-02927-1_40 . ISBN   978-3-642-02926-4.
  8. 1 2 Bose, Prosenjit; Kranakis, Evangelos; Morin, Pat; Tang, Yihui (2005). "Consultas aproximadas de moda y mediana de rango" (PDF) . Stacs 2005. Lecture Notes in Computer Science. Vol. 3404. pp. 377–388 . doi : 10.1007/978-3-540-31856-9_31 . ISBN   978-3-540-24998-6.
  9. ↑ Boyer, Robert S.; Moore, J. Strother (1991). "MJRTY: Un algoritmo rápido de votación por mayoría" . Razonamiento automatizado . Serie de razonamiento automatizado. Vol. 1. Dordrecht: Springer Netherlands. págs. 105–117 . doi : 10.1007/978-94-011-3488-0_5 . ISBN   978-94-010-5542-0. Consultado el 18 de diciembre de 2021 .
  10. ↑ Misra, J.; Gries, David (noviembre de 1982). "Finding repeated elements" . Science of Computer Programming . 2 (2): 143– 152. doi : 10.1016/0167-6423(82)90012-0 . hdl : 1813/6345 . ISSN 0167-6423 . 
  11. ^ Karpiński , Marek. Buscando colores frecuentes en rectángulos . OCLC 277046650 . 
  12. ↑ Gagie, Travis; He, Meng; Munro, J. Ian; Nicholson, Patrick K. (2011). "Finding Frequent Elements in Compressed 2D Arrays and Strings" . String Processing and Information Retrieval . Lecture Notes in Computer Science. Vol. 7024. Berlín, Heidelberg: Springer Berlin Heidelberg. pp. 295–300 . doi : 10.1007/978-3-642-24583-1_29 . ISBN   978-3-642-24582-4. Consultado el 18 de diciembre de 2021 .
  13. 1 2 3 Chan, Timothy M.; Durocher, Stephane; Skala, Matthew; Wilkinson, Bryan T. (2012). "Estructuras de datos en espacio lineal para consultas de minoría de rango en arreglos" . Algorithm Theory – SWAT 2012. Lecture Notes in Computer Science. Vol. 7357. Berlín, Heidelberg: Springer Berlin Heidelberg. pp. 295–306 . doi : 10.1007/978-3-642-31155-0_26 . ISBN   978-3-642-31154-3. Consultado el 20 de diciembre de 2021 .
  14. ↑ Sadakane, Kunihiko; Navarro, Gonzalo (17 de enero de 2010). «Árboles sucintos totalmente funcionales». Actas del Vigésimo Primer Simposio Anual ACM-SIAM sobre Algoritmos Discretos . Filadelfia, PA: Society for Industrial and Applied Mathematics. págs. 134–149 . doi : 10.1137/1.9781611973075.13 . ISBN  978-0-89871-701-3. S2CID 3189222 . 
  15. ↑ Chan, Timothy M.; Durocher, Stephane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (2013-03-08). "Estructuras de datos de espacio lineal para consultas en modo rango en matrices" . Theory of Computing Systems . 55 (4): 719– 741. doi : 10.1007/s00224-013-9455-2 . ISSN 1432-4350 . S2CID 253747004 .  
  16. 1 2 3 Gagie, Travis; He, Meng; Navarro, Gonzalo; Ochoa, Carlos (septiembre de 2020). "Estructuras de datos de mayoría de ruta de árbol" . Theoretical Computer Science . 833 : 107–119 . arXiv : 1806.01804 . doi : 10.1016/j.tcs.2020.05.039 . ISSN 0304-3975 . 
  17. ↑ He, Meng; Munro, J. Ian; Zhou, Gelin (2014-07-08). "Un marco para árboles ordinales etiquetados sucintos sobre alfabetos grandes" . Algorithmica . 70 (4): 696– 717. doi : 10.1007/s00453-014-9894-4 . ISSN 0178-4617 . S2CID 253977813 .  
  • Estructuras de datos abiertas - Capítulo 13 - Estructuras de datos para números enteros
  • Estructuras de datos para consultas de rango medio - Gerth Stolting Brodal y Allan Gronlund Jorgensen
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Array (data structure)In computer science , an array is a data structure consisting of a collection of elements ( values or variables ), of same memory size, each identi...Función (programación informática)Función (programación informática)En programación informática , una función (también procedimiento , método , subrutina , rutina o subprograma ) es una unidad invocable [1] de lógic...Complejidad temporalComplejidad temporalEn informática teórica , la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que tarda un ordenador en ejecu...Complejidad espacialLa complejidad espacial de un algoritmo o una estructura de datos es la cantidad de espacio de memoria requerida para resolver una instancia del pr...Operación binariaOperación binariaEn matemáticas , una operación binaria u operación diádica es una regla para combinar dos elementos (llamados operandos ) para producir otro elemen...