Consulta de rango (estructuras de datos)

En las 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 han sido ampliamente estudiados 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.

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 .${\ Displaystyle q_ {f} (A, i, j)}$${\ Displaystyle A = [a_ {1}, a_ {2}, .., a_ {n}]}$${\ Displaystyle A [1, n]}$${\ Displaystyle 1 \ leq i \ leq j \ leq n}$${\ Displaystyle f (A [i, j]) = f (a_ {i}, \ ldots, a_ {j})}$

Por ejemplo, para y una matriz de números, la consulta de rango calcula , para cualquier . Estas consultas pueden responderse en tiempo constante y utilizando espacio extra calculando las sumas de los primeros i elementos de A y almacenándolos en una matriz auxiliar B , de manera que contenga la suma de los primeros i elementos de A para cada . Por lo tanto, cualquier consulta puede responderse haciendo .${\ Displaystyle f = \ sum}$${\ Displaystyle A [1, n]}$${\ Displaystyle \ sum _ {i, j} A}$${\ Displaystyle \ sum A [i, j] = (a_ {i} + \ ldots + a_ {j})}$${\ Displaystyle 1 \ leq i \ leq j \ leq n}$${\ Displaystyle O (n)}$${\ Displaystyle B [i]}$${\ Displaystyle 0 \ leq i \ leq n}$${\ Displaystyle \ sum A [i, j] = B [j] -B [i-1]}$

Esta estrategia puede extenderse para todos los operadores de grupo f donde la noción de está bien definida y es fácilmente computable. ^[1] Finalmente, esta solución se puede extender a matrices bidimensionales con un preprocesamiento similar. ^[2]${\ displaystyle f ^ {- 1}}$

Consulta mínima de rango reducida al problema de ancestro común más bajo .