Consulta de rango (informática)

En informática , el problema de consulta de rango consiste en responder eficientemente varias consultas respecto de un intervalo determinado de elementos dentro de una matriz . Por ejemplo, una tarea común, conocida como consulta de rango mínimo , es encontrar el valor más pequeño dentro de un rango determinado dentro de una lista de números.

Definición

Dada una función que acepta una matriz, una consulta de rango en una matriz toma dos índices y devuelve el resultado cuando se aplica a la submatriz . Por ejemplo, para una función que devuelve la suma de todos los valores de una matriz, la consulta de rango devuelve la suma de todos los valores del rango . ^{[ cita necesaria ]} ${\displaystyle f}$ ${\displaystyle f_{q}(l,r)}$ ${\displaystyle a=[a_{1},..,a_{n}]}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle [a_{l},\ldots ,a_{r}]}$ ${\displaystyle \operatorname {sum} }$ ${\displaystyle \operatorname {sum} _{q}(l,r)}$ ${\displaystyle [l,r]}$

Soluciones

Matriz de suma de prefijos

Las consultas de suma de rango se pueden responder en tiempo constante y espacio lineal calculando previamente 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 . Luego, cualquier consulta se puede calcular de la siguiente manera: $${\displaystyle \operatorname {sum} _{q}(l,r)=p_{r}-p_{l-1}.}$$

Esta estrategia puede extenderse a cualquier otra operación binaria cuya función inversa esté bien definida y sea fácilmente computable. ^[1] También se puede ampliar 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 , entonces ${\displaystyle f}$ ${\displaystyle f^{-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 difícil del problema consiste en ejecutar consultas de rango sobre datos dinámicos; es decir, datos que pueden mutar entre cada consulta. Para actualizar de manera eficiente los valores de la matriz, se necesitan estructuras de datos más sofisticadas como el árbol de segmentos o el árbol de Fenwick . ^{[ cita necesaria ]}

Ejemplos

Operadores de semigrupo

Consulta de rango mínimo reducida al problema de 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 de no siempre está definida, 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 permite responder consultas de rango en listas donde f es un operador de semigrupo en el tiempo, donde es un cierto inverso funcional de la función de Ackermann . ${\displaystyle f^{-1}}$ ${\displaystyle \Theta (c\cdot n)}$ ${\displaystyle \theta (\alpha _{c}(n))}$ ${\displaystyle \alpha _{c}}$

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

El árbol cartesiano de una matriz tiene como raíz y como subárboles izquierdo y derecho el árbol cartesiano de y el árbol cartesiano de respectivamente. Una consulta de rango mínimo es el ancestro común más bajo en of y . Debido a que el ancestro común más bajo se puede resolver en tiempo constante utilizando un preprocesamiento de tiempo y espacio , la consulta de rango mínimo también puede hacerlo. La solución cuando es análoga. Los árboles cartesianos se pueden construir en tiempo lineal . ${\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]}$ ${\textstyle \min _{i,j}(A)}$ ${\displaystyle T_{A}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{j}}$ ${\displaystyle O(n)}$ ${\displaystyle f=\max }$

Modo

La moda de un array es el elemento que más aparece en él. Por ejemplo, la moda de es ${\displaystyle a=[4,5,6,7,4]}$4 . En caso de empate, se podrá elegir como moda cualquiera de los elementos más frecuentes. Una consulta de modo de rango consiste en un preprocesamiento de modo que podamos encontrar el modo en cualquier rango de . Se han ideado varias estructuras de datos para resolver este problema, resumimos algunos de los resultados en la siguiente tabla. ^[1] ${\displaystyle A[1,n]}$ ${\displaystyle A[1,n]}$

Recientemente Jørgensen et al. demostró un límite inferior en el modelo de sonda celular para cualquier estructura de datos que utilice células S. ^[4] ${\displaystyle \Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)}$

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 , se puede resolver en O ( n ), utilizando el algoritmo de 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 rango donde A,i y j tienen los significados habituales devuelve el elemento mediano de . De manera equivalente, debería devolver el elemento de rango . Las consultas sobre la mediana del rango no se pueden resolver siguiendo ninguno de los métodos anteriores discutidos anteriormente, incluido el enfoque de Yao para operadores de semigrupo. ^[8] ${\displaystyle \operatorname {median} (A,i,j)}$ ${\displaystyle A[i,j]}$ ${\displaystyle \operatorname {median} (A,i,j)}$ ${\displaystyle A[i,j]}$ ${\displaystyle {\frac {j-i}{2}}}$

Se han estudiado dos variantes de este problema, la versión fuera de línea , donde todas las k consultas de interés se dan 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 con tiempo y espacio. ${\displaystyle O(n\log k+k\log n)}$ ${\displaystyle O(n\log k)}$

El siguiente pseudocódigo del algoritmo de selección rápida muestra cómo encontrar el elemento de rango r en una matriz sin clasificar de elementos distintos, para encontrar las medianas de rango que establecemos . ^[7] ${\displaystyle A[i,j]}$ ${\displaystyle r={\frac {j-i}{2}}}$

rangeMedian(A, i, j, r) { si A.length() == 1 return A[1] si A.low no está definido entonces m = mediana(A) A.bajo = [e en A | mi <= metro] A.alto = [e en A | mi > m ] calcular t el número de elementos de A[i, j] que pertenecen a A.low si r <= t entonces  devuelve rangoMediano(A.bajo, i, j, r) en caso contrario  devuelve rangoMediano(A.alto, 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 que terminan en es y este número es mayor que entonces debemos seguir buscando el elemento de rango en ; de lo contrario deberíamos buscar el elemento de rango en . Para encontrar t , basta con encontrar el índice máximo tal que está en y el índice máximo tal que está en . Entonces . El costo total de cualquier consulta, sin considerar la parte de partición, es porque como máximo se realizan llamadas recursivas y solo se realiza un número constante de operaciones en cada una de ellas (para obtener el valor de t se debe utilizar cascada fraccionaria ). Si se utiliza un algoritmo lineal para encontrar las medianas, el costo total del preprocesamiento para consultas de medianas de rango k es . El algoritmo también se puede modificar para resolver la versión en línea del problema. ^[7] ${\displaystyle A[i,j]}$A.lowtrrA.low ${\displaystyle (r-t)}$A.high ${\displaystyle m\leq i-1}$ ${\displaystyle a_{m}}$A.low ${\displaystyle l\leq j}$ ${\displaystyle a_{l}}$A.high ${\displaystyle t=l-m}$ ${\displaystyle \log n}$ ${\displaystyle \log n}$ ${\displaystyle n\log k}$

Mayoría

Encontrar elementos frecuentes en un conjunto determinado 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 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 importancia para detectar dichos elementos. Boyer y Moore ^[9] propusieron uno de los algoritmos más famosos para encontrar la mayoría de una matriz, que también se conoce como algoritmo de voto mayoritario de Boyer-Moore . Boyer y Moore propusieron un algoritmo para encontrar el elemento mayoritario de una cadena (si lo tiene) en el tiempo y utilizando el 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 usando comparaciones para encontrar todos los elementos en una matriz cuyas frecuencias relativas sean mayores que algún umbral . Una consulta de mayoría de rango es aquella que, dado un subrango de una estructura de datos (por ejemplo, una matriz) de tamaño , devuelve el conjunto de todos los elementos distintos que aparecen más de (o en algunas publicaciones iguales) veces en ese rango determinado. En diferentes estructuras que admiten consultas de mayoría de rango, pueden ser estáticas (especificadas durante el preprocesamiento) o dinámicas (especificadas 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 determinado rango podría haber como mucho candidatos distintos con frecuencias relativas de al menos . Al verificar cada uno de estos candidatos en tiempo constante, se logra el tiempo de consulta. Una consulta de mayoría de rango es descomponible ^[11] en el sentido de que una mayoría en un rango con particiones y debe ser una mayoría en o . Debido a esta capacidad de descomposición, algunas estructuras de datos responden a la mayoría de consultas en matrices unidimensionales encontrando el ancestro común más bajo (LCA) de los puntos finales del rango de consulta en un árbol de rango y validando dos conjuntos de candidatos (de tamaño ) de cada punto final. al ancestro común más bajo en un tiempo constante, lo que genera un tiempo de consulta. ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle O\left(n\log \left({\frac {1}{\tau }}\right)\right)}$ ${\displaystyle 0<\tau <1}$ ${\displaystyle \tau }$ ${\displaystyle |R|}$ ${\displaystyle \tau |R|}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle \tau }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle R}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle \tau }$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle \tau }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O(1/\tau )}$

matrices bidimensionales

Gagie y col. ^[12] propusieron una estructura de datos que admite consultas de mayoría de rango en una matriz . Para cada consulta en esta estructura de datos se especifica un umbral y un rango rectangular , y el conjunto de todos los elementos que tienen frecuencias relativas (dentro de ese rango rectangular) mayores o iguales se devuelven como salida. Esta estructura de datos admite umbrales dinámicos (especificados en el momento de la consulta) y un umbral de preprocesamiento en función del cual se construye. Durante el preprocesamiento, se construye un conjunto de intervalos verticales y horizontales en la matriz. Juntos, un intervalo vertical y otro horizontal forman un bloque. Cada bloque forma 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 se almacena un conjunto de candidatos (con elementos como máximo) que consta de elementos que tienen frecuencias relativas al menos (el umbral de preprocesamiento como se mencionó 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 en un bloque debe aparecer su conjunto de candidatos. Cada consulta mayoritaria se responde primero encontrando el bloque de consulta, o el bloque más grande contenido en el rectángulo de consulta proporcionado en el tiempo. Para el bloque de consulta obtenido, los primeros candidatos se devuelven (sin ser verificados) a tiempo, por lo que este proceso podría arrojar algunos falsos positivos. Muchas otras estructuras de datos (como se analiza a continuación) han propuesto métodos para verificar cada candidato en un tiempo constante y así mantener el tiempo de consulta sin arrojar falsos positivos. Los casos en los que el bloque de consulta es más pequeño se manejan almacenando diferentes instancias de esta estructura de datos de la siguiente forma: ${\displaystyle \tau }$ ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}$ ${\displaystyle 0<\tau <1}$ ${\displaystyle \operatorname {R} }$ ${\displaystyle \tau }$ ${\displaystyle \alpha }$ ${\displaystyle m\times n}$ ${\displaystyle {\frac {9}{\alpha }}}$ ${\displaystyle {\frac {\alpha }{9}}}$ ${\displaystyle \alpha }$ ${\displaystyle \tau }$ ${\displaystyle O(1)}$ ${\displaystyle {\frac {9}{\tau }}}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle 1/\alpha }$ ${\displaystyle \log \left({\frac {1}{\alpha }}\right)}$

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

¿Dónde está el umbral de preprocesamiento de la -ésima instancia? Por lo tanto, para bloques de consulta más pequeños que la -ésima instancia, se consulta. Como se mencionó anteriormente, esta estructura de datos tiene tiempo de consulta y requiere bits de espacio al almacenar una copia codificada por Huffman (tenga en cuenta el factor y también consulte Codificación de Huffman ). ${\displaystyle \beta }$ ${\displaystyle i}$ ${\displaystyle 1/\alpha }$ ${\displaystyle \lceil \log(1/\tau )\rceil }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}$ ${\displaystyle \log({\frac {1}{\alpha }})}$

matrices unidimensionales

Chan et al. ^[13] propusieron una estructura de datos que, dada una matriz unidimensional , un subrango de (especificado en el momento de la consulta) y un umbral (especificado en el momento de la consulta), es capaz de devolver la lista de todas las mayorías en el tiempo que requieren 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 de tiempo que requiere palabras de espacio. Para una matriz unidimensional , deje que una consulta de rango superior k unilateral tenga la forma . Para un rango máximo de rangos en los que la frecuencia de un elemento distinto permanece sin cambios (e igual a ), se construye un segmento de línea horizontal. El intervalo de este segmento de línea corresponde a y tiene un valor igual a . Dado que agregar cada elemento cambia la frecuencia de exactamente un elemento distinto, el proceso antes mencionado crea segmentos de línea. Además, para una línea vertical, todos los segmentos de línea horizontal que la cruzan se ordenan según sus frecuencias. Tenga en cuenta que cada segmento de línea horizontal con intervalo corresponde exactamente a un elemento distinto en , de modo que . Luego, se puede responder a una consulta top-k disparando un rayo vertical e informando los primeros segmentos de línea horizontal que lo cruzan (recuerde desde arriba que estos segmentos de línea ya están ordenados según sus frecuencias) en el tiempo. ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(k)}$ ${\displaystyle O(n)}$ ${\displaystyle A[0,..,n-1]}$ ${\displaystyle A[0..i]{\text{ for }}0\leq i\leq n-1}$ ${\displaystyle A[0..i]{\text{ through }}A[0..j]}$ ${\displaystyle e}$ ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle [i,j]}$ ${\displaystyle y}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle O(n)}$ ${\displaystyle x=i}$ ${\displaystyle x}$ ${\displaystyle [\ell ,r]}$ ${\displaystyle e}$ ${\displaystyle A}$ ${\displaystyle A[\ell ]=e}$ ${\displaystyle x=i}$ ${\displaystyle k}$ ${\displaystyle O(k)}$

Chan et al. ^[13] primero construya un árbol de rango en el que cada nodo de ramificación almacene una copia de la estructura de datos descrita anteriormente para consultas top-k de rango unilateral y cada hoja represente un elemento de . 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á destinada a responder consultas top-k de rango unilateral. Tenga en cuenta que para una matriz unidimensional , se puede construir un árbol de rango dividiéndolo en dos mitades y recurriendo en ambas mitades; por lo tanto, cada nodo del árbol de rango resultante representa un rango. También se puede ver que este árbol de rango requiere palabras de espacio, porque hay niveles y cada nivel tiene nodos. Además, dado que en cada nivel de un árbol de rango todos los nodos tienen un total de elementos en sus subárboles y que hay niveles, la complejidad espacial de este árbol de rango es . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle \ell }$ ${\displaystyle 2^{\ell }}$ ${\displaystyle \ell }$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n\log n)}$

Usando esta estructura, una consulta de mayoría de rango sobre with se responde de la siguiente manera. Primero, el ancestro común más bajo (LCA) de los nodos de las hojas y se encuentra en tiempo constante. Tenga en cuenta que existe una estructura de datos que requiere bits de espacio y que es capaz de responder a las consultas del ACV a tiempo. ^[14] Denotemos el ACV de y , utilizando y de acuerdo con la descomponibilidad de las consultas de mayoría de rango (como se describe arriba y en ^[11] ), la consulta de rango de dos lados se puede convertir en dos rangos de un solo lado top-k consultas (desde hasta y ). Estas dos consultas top-k de rango unilateral devuelven los elementos top-( ) más frecuentes en cada uno de sus respectivos rangos en el tiempo. Estos elementos frecuentes conforman el conjunto de candidatos a mayorías en las que hay candidatos algunos de los cuales podrían ser falsos positivos. Luego, cada candidato se evalúa 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 el tiempo si un subrango dado de una matriz contiene o no al menos instancias de un elemento particular. . ${\displaystyle \tau }$ ${\displaystyle A[i..j]}$ ${\displaystyle A[0..n-1]}$ ${\displaystyle 0\leq i\leq j\leq n}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle z}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle z}$ ${\displaystyle \tau }$ ${\displaystyle A[i..j]}$ ${\displaystyle z}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle 1/\tau }$ ${\displaystyle O(1/\tau )}$ ${\displaystyle \tau }$ ${\displaystyle A[i..j]}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O(1)}$ ${\displaystyle A}$ ${\displaystyle q}$ ${\displaystyle e}$

Caminos de árboles

Gagie y cols. ^[16] propusieron una estructura de datos que admite consultas tales que, dados dos nodos y en un árbol, pueden reportar la lista de elementos que tienen una frecuencia relativa mayor que en el camino de a . Más formalmente, sea un árbol etiquetado en el que cada nodo tiene una etiqueta de un alfabeto de tamaño . Denotemos la etiqueta del nodo en . Denotemos la ruta única desde hasta en la que se enumeran los nodos intermedios en el orden en que se visitan. Dado y un umbral fijo (especificado durante el preprocesamiento) , una consulta debe devolver el conjunto de todas las etiquetas que aparecen más de veces en . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \tau }$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle \sigma }$ ${\displaystyle label(u)\in [1,\dots ,\sigma ]}$ ${\displaystyle u}$ ${\displaystyle T}$ ${\displaystyle P_{uv}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle 0<\tau <1}$ ${\displaystyle Q(u,v)}$ ${\displaystyle \tau |P_{uv}|}$ ${\displaystyle P_{uv}}$

Para construir esta estructura de datos, se marcan los primeros nodos . Esto se puede hacer marcando cualquier nodo que tenga una distancia al menos desde la parte inferior de los tres (altura) y cuya profundidad sea divisible por . Después de hacer esto, se puede observar que la distancia entre cada nodo y su ancestro marcado más cercano es menor que . Para un nodo marcado , se almacenan diferentes secuencias (rutas hacia la raíz) , ${\displaystyle {O}(\tau n)}$ ${\displaystyle \lceil 1/\tau \rceil }$ ${\displaystyle \lceil 1/\tau \rceil }$ ${\displaystyle 2\lceil 1/\tau \rceil }$ ${\displaystyle x}$ ${\displaystyle \log(depth(x))}$ ${\displaystyle P_{i}(x)}$

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

for donde devuelve la etiqueta del padre directo del nodo . Dicho de otra manera, para cada nodo marcado, se almacena el conjunto de todos los caminos con una potencia de dos de longitud (más uno para el nodo en sí) hacia la raíz. Además, para cada uno , se almacena el conjunto de todos los candidatos mayoritarios. Más específicamente, contiene el conjunto de todas las mayorías o etiquetas que aparecen más de veces en . Es fácil ver que el conjunto de candidatos puede tener como máximo etiquetas distintas para cada uno . Gagie y col. ^[16] luego observe que el conjunto de todas las mayorías en el camino desde cualquier nodo marcado hasta uno de sus antepasados ​​está incluido en some (Lema 2 en ^[16] ) ya que la longitud de es igual a, por lo tanto, existe un para cuya longitud es entre donde está la distancia entre x y z. La existencia de tales implica que una mayoría en el camino desde a debe ser una mayoría en y, por lo tanto, debe aparecer en . Es fácil ver que esta estructura de datos requiere palabras de espacio, porque como se mencionó anteriormente en la fase de construcción, los nodos se marcan y para cada nodo marcado se almacenan algunos conjuntos candidatos. Por definición, para cada nodo marcado de dichos conjuntos hay almacenes, cada uno de los cuales contiene candidatos. Por lo tanto, esta estructura de datos requiere palabras con espacio. Tenga en cuenta que cada nodo también almacena lo que es igual al número de instancias de en la ruta desde la raíz de , esto no aumenta la complejidad del espacio ya que solo agrega un número constante de palabras por nodo. ${\displaystyle 0\leq i\leq \log(depth(x))}$ ${\displaystyle \operatorname {par} (x)}$ ${\displaystyle x}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle (\tau /2)}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle (\tau /2).(2^{i}+1)}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle 2/\tau }$ ${\displaystyle i}$ ${\displaystyle \tau }$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle (2^{i}+1)}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle 0\leq i\leq \log(depth(x))}$ ${\displaystyle d_{xz}{\text{ and }}2d_{xz}}$ ${\displaystyle d_{xz}}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle \tau }$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle (\tau /2)}$ ${\displaystyle P_{i}(x)}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(\tau n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}$ ${\displaystyle x}$ ${\displaystyle count(x)}$ ${\displaystyle label(x)}$ ${\displaystyle x}$ ${\displaystyle T}$

Cada consulta entre dos nodos se puede responder utilizando la propiedad de descomponibilidad (como se explicó anteriormente) de las consultas de mayoría de rango y dividiendo la ruta de consulta entre y en cuatro subrutas. Sea el ancestro común más bajo de y , siendo y los ancestros marcados más cercanos de y respectivamente. El camino desde a se descompone en los caminos desde y hacia y respectivamente (el tamaño de estos caminos es más pequeño que, por definición, todos los cuales se consideran candidatos) y los caminos desde y hacia (encontrando el adecuado como se explicó anteriormente y considerando todas sus etiquetas como candidatas). Tenga en cuenta que los nodos de límite deben manejarse en consecuencia para que todos estos subtrayectos sean separados y de todos ellos se derive un conjunto de candidatos. Luego, cada uno de estos candidatos se verifica utilizando una combinación de la consulta que devuelve el ancestro más bajo del nodo que tiene etiqueta y los campos de cada nodo. Con una RAM de bits y un alfabeto de tamaño , la consulta se puede responder a tiempo teniendo requisitos de espacio lineal. ^[17] Por lo tanto, verificar cada uno de los candidatos a tiempo da como resultado el tiempo total de consulta para devolver el conjunto de todas las mayorías en el camino de a . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \tau }$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle z}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle 2\lceil 1/\tau \rceil }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle C_{i}(x)}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle labelanc(x,\ell )}$ ${\displaystyle x}$ ${\displaystyle \ell }$ ${\displaystyle count(x)}$ ${\displaystyle w}$ ${\displaystyle \sigma }$ ${\displaystyle labelanc(x,\ell )}$ ${\displaystyle O\left(\log \log _{w}\sigma \right)}$ ${\displaystyle O(1/\tau )}$ ${\displaystyle O\left(\log \log _{w}\sigma \right)}$ ${\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}$ ${\displaystyle \tau }$ ${\displaystyle u}$ ${\displaystyle v}$

Problemas relacionados

Todos los problemas descritos anteriormente han sido estudiados 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 de ancestro de nivel . Una familia similar de problemas son las consultas de rango ortogonal , también conocidas como consultas de conteo.

Ver también

• Problema de ancestro de nivel
• Antepasado común más bajo

Referencias

1. Krizanc, Danny; Morín, Pat ; Smid, Michiel HM (2003). "Consultas de modo de rango y mediana de rango en listas y árboles". ISAAC : 517–526. arXiv : cs/0307034 . Código Bib : 2003cs.......7034K.
2. Meng, él; Munro, J. Ian; Nicholson, Patrick K. (2011). "Selección de rango dinámico en espacio lineal". ISAAC : 160–169. arXiv : 1106.5076 .
3. Yao, AC (1982). "Compensación espacio-temporal para responder consultas de rango". E 14º Simposio Anual ACM sobre Teoría de la Computación : 128–136.
4. Greve, M; J{\o}rgensen, A.; Larsen, K.; Truelsen, J. (2010). "Límites inferiores de la sonda celular y aproximaciones para el modo de rango". Autómatas, lenguajes y programación : 605–616.
5. Har-Peled, Sariel ; Muthukrishnan, S. (2008). "Medianas de rango". ESA : 503–514.
6. Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (agosto de 1973). «Plazos de tiempo para la selección» (PDF) . Revista de Ciencias de la Computación y de Sistemas . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 .
7. Beat, Gfeller; Lijadoras, Peter (2009). "Hacia las medianas del rango óptimo". Icalp (1) : 475–486. arXiv : 0901.1761 .
8. Bose, P ; Kranakis, E.; Morín, P .; Tang, Y. (2005). "Consultas de modo de rango aproximado y mediana de rango". En Actas del 22º Simposio sobre aspectos teóricos de la informática (STACS 2005), volumen 3404 de Lecture Notes in ComputerScience : 377–388.
9. Boyer, Robert S.; Moore, J. Strother (1991), "MJRTY: un algoritmo de voto mayoritario rápido", Razonamiento automatizado, Serie de razonamiento automatizado, vol. 1, Dordrecht: Springer Países Bajos, págs. 105–117, doi :10.1007/978-94-011-3488-0_5, ISBN 978-94-010-5542-0, recuperado el 18 de diciembre de 2021
10. Misra, J.; Gries, David (noviembre de 1982). "Encontrar elementos repetidos". Ciencia de la programación informática . 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; Él, Meng; Munro, J. Ian; Nicholson, Patrick K. (2011), "Encontrar elementos frecuentes en cadenas y matrices 2D comprimidas", Procesamiento de cadenas y recuperación de información , Apuntes de conferencias sobre informática, vol. 7024, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 295–300, doi :10.1007/978-3-642-24583-1_29, ISBN 978-3-642-24582-4, recuperado el 18 de diciembre de 2021
13. Chan, Timothy M.; Durocher, Stéphane; Skala, Mateo; Wilkinson, Bryan T. (2012), "Estructuras de datos de espacio lineal para consultas de minorías de rango en matrices", Teoría de algoritmos - SWAT 2012 , Apuntes de conferencias en informática, vol. 7357, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 295–306, doi :10.1007/978-3-642-31155-0_26, ISBN 978-3-642-31154-3, recuperado 2021-12-20
14. Sadakane, Kunihiko; Navarro, Gonzalo (17 de enero de 2010). "Árboles concisos completamente funcionales". Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas: 134–149. doi : 10.1137/1.9781611973075.13 . ISBN 978-0-89871-701-3. S2CID  3189222.
15. Chan, Timothy M.; Durocher, Stéphane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (8 de marzo de 2013). "Estructuras de datos de espacio lineal para consulta en modo de rango en matrices". Teoría de los Sistemas Computacionales . 55 (4): 719–741. doi :10.1007/s00224-013-9455-2. ISSN  1432-4350. S2CID  253747004.
16. Gagie, Travis; Él, Meng; Navarro, Gonzalo; Ochoa, Carlos (septiembre 2020). "Estructuras de datos mayoritarias de rutas de árboles". Informática Teórica . 833 : 107-119. arXiv : 1806.01804 . doi : 10.1016/j.tcs.2020.05.039. ISSN  0304-3975.
17. Él, Meng; Munro, J. Ian; Zhou, Gelin (8 de julio de 2014). "Un marco para árboles ordinales etiquetados sucintos sobre alfabetos grandes". Algorítmica . 70 (4): 696–717. doi :10.1007/s00453-014-9894-4. ISSN  0178-4617. S2CID  253977813.

enlaces externos

• Estructura de datos abierta - Capítulo 13 - Estructuras de datos para enteros
• Estructuras de datos para consultas de rango medio - Gerth Stolting Brodal y Allan Gronlund Jorgensen