En estructuras de datos , una consulta de rango consiste en preprocesar algunos datos de entrada en una estructura de datos para responder de manera eficiente cualquier número de consultas en cualquier subconjunto de la entrada. En particular, hay un grupo de problemas que se han estudiado extensamente donde la entrada es una matriz de números sin clasificar y una consulta consiste en calcular alguna función, como el mínimo, en un rango específico de la matriz.
Definición
Una consulta de rango en una matriz de n elementos de algún conjunto S , denotado, toma dos índices , una función f definida sobre matrices de elementos de S y salidas.
Por ejemplo, para y una matriz de números, la consulta de rango calcula , para cualquier . Estas consultas pueden ser respondidas en tiempo constante y utilizandoespacio extra calculando las sumas de los primeros i elementos de A y almacenándolos en una matriz auxiliar B , de modo quecontiene la suma de los primeros i elementos de A para cada. Por lo tanto, cualquier consulta se puede responder haciendo.
Esta estrategia puede extenderse para todos los operadores de grupo f donde la noción deestá bien definido y es fácilmente computable. [1] Finalmente, esta solución se puede extender a matrices bidimensionales con un preprocesamiento similar. [2]
Ejemplos de
Operadores de semigrupo
Cuando la función de interés en una consulta de rango es un operador de semigrupo , la noción deno 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 c constante , un preprocesamiento de tiempo y espaciopermite responder consultas de rango en listas donde f es un operador de semigrupo en tiempo, donde es un cierto inverso funcional de la función de Ackermann .
Hay algunos operadores de semigrupo que admiten soluciones ligeramente mejores. Por ejemplo cuando. Asumir luego devuelve el índice del elemento mínimo de. Luegodenota la consulta de rango mínimo correspondiente. Existen varias estructuras de datos que permiten responder una consulta mínima de rango en tiempo usando un preprocesamiento de tiempo y espacio . Una de estas soluciones se basa en la equivalencia entre este problema y el problema del antepasado común más bajo .
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 mínima de rangoes el antepasado común más bajo en de y . Porque el antepasado común más bajo se puede resolver en tiempo constante utilizando un preprocesamiento de tiempo y espacio., la consulta mínima de rango también puede. La solución cuandoes análogo. Los árboles cartesianos se pueden construir en tiempo lineal .
Modo
El modo de una matriz A es el elemento que aparece más en A . Por ejemplo, el modo de es 4 . En caso de empates, se puede elegir como modo cualquiera de los elementos más frecuentes. Una consulta en modo de rango consiste en preprocesar 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]
Espacio | Tiempo de consulta | Restricciones |
---|---|---|
Recientemente, Jørgensen et al. demostró un límite inferior en el modelo de sonda celular depara 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 , se puede resolver en O ( n ), utilizando el algoritmo de la mediana de las medianas . [6] Sin embargo, su generalización a través de consultas de mediana de rango es reciente. [7] Una consulta de mediana de rangodonde A, i y j tienen los significados habituales devuelve el elemento mediano de. Equivalentemente, debería devolver el elemento de de rango . 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 offline , 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.
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]
rangeMedian (A, i, j, r) { if A.length () == 1 return 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] calcule t 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 rangeMedian
divide A
, usando A
la mediana de ', en dos matrices A.low
y A.high
, donde la primera contiene los elementos de A
que son menores o iguales que la mediana m
y la última el resto de los elementos de A
. Si sabemos que el número de elementos deque terminan en A.low
es t
y este número es mayor de lo r
que deberíamos seguir buscando el elemento de rango r
en A.low
; de lo contrario deberíamos buscar el elemento de rangoen A.high
. Para encontrar t , es suficiente encontrar el índice máximo tal que está en A.low
y el índice máximo tal que está en A.high
. Luego. El costo total de cualquier consulta, sin considerar la parte de partición, es ya que a lo sumo Se realizan llamadas de recursividad y solo se realiza un número constante de operaciones en cada una de ellas (para obtener el valor de t se debe usar una cascada fraccional ). Si se usa un algoritmo lineal para encontrar las medianas, el costo total de 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]
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 pueden 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 ortogonal , también conocidas como consultas de recuento.
Ver también
Referencias
- ↑ a b Krizanc, Danny; Morin, Pat ; Smid, Michiel HM (2003). "Consultas de modo de rango y mediana de rango en listas y árboles" . ISAAC : 517–526. arXiv : cs / 0307034 .
- ^ Meng, He; Munro, J. Ian; Nicholson, Patrick K. (2011). "Selección de rango dinámico en espacio lineal". ISAAC : 160–169.
- ^ Yao, A. C (1982). "Compensación de espacio-tiempo para responder consultas de rango". E XIV Simposio anual de ACM sobre teoría de la computación : 128-136.
- ^ Greve, M; J {\ o} rgensen, A .; Larsen, K .; Truelsen, J. (2010). "Límites inferiores de la sonda de celda y aproximaciones para el modo de rango". Autómatas, lenguajes y programación : 605–616.
- ^ Har-Peled, Sariel ; Muthukrishnan, S. (2008). "Medianas de rango". ESA : 503–514.
- ^ Blum, M .; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (agosto de 1973). "Plazos de selección" (PDF) . Revista de Ciencias de la Computación y Sistemas . 7 (4): 448–461. doi : 10.1016 / S0022-0000 (73) 80033-9 .
- ^ a b c Beat, Gfeller; Sanders, Peter (2009). "Hacia las medianas de rango óptimo". Icalp (1) : 475–486.
- ^ a b Bose, P ; Kranakis, E .; Morin, 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.
enlaces externos
- Estructura de datos abierta - Capítulo 13 - Estructuras de datos para enteros
- Estructuras de datos para consultas de mediana de rango: Gerth Stolting Brodal y Allan Gronlund Jorgensen