Consulta de mínimo en un rango (Range Minimum Query)

Se da un arreglo $A[1..N]$ . Hay que responder consultas entrantes de la forma $(L, R)$ , que piden hallar el elemento mínimo en el arreglo $A$ entre las posiciones $L$ y $R$ inclusive.

RMQ puede aparecer en problemas de forma directa o aplicarse en otras tareas, p. ej. el problema del ancestro común más bajo (Lowest Common Ancestor).

Solución

Hay muchos enfoques posibles y estructuras de datos que se pueden usar para resolver la tarea RMQ.

Los que se explican en este sitio se listan a continuación.

Primero los enfoques que permiten modificaciones del arreglo entre las respuestas a las consultas.

Descomposición por raíz cuadrada - responde cada consulta en $O(\sqrt{N})$ , preprocesamiento en $O(N)$ . Pros: una estructura de datos muy sencilla. Contras: peor complejidad.
Árbol de Segmentos - responde cada consulta en $O(\log N)$ , preprocesamiento en $O(N)$ . Pros: buena complejidad temporal. Contras: mayor cantidad de código en comparación con las otras estructuras de datos.
Árbol de Fenwick - responde cada consulta en $O(\log N)$ , preprocesamiento en $O(N \log N)$ . Pros: el código más corto, buena complejidad temporal. Contras: el Árbol de Fenwick solo se puede usar para consultas con $L = 1$ , así que no es aplicable a muchos problemas.

Y aquí están los enfoques que solo funcionan sobre arreglos estáticos, es decir, no es posible cambiar un valor del arreglo sin recomputar toda la estructura de datos.

Tabla Dispersa - responde cada consulta en $O(1)$ , preprocesamiento en $O(N \log N)$ . Pros: estructura de datos sencilla, excelente complejidad temporal.
Árbol Sqrt - responde consultas en $O(1)$ , preprocesamiento en $O(N \log \log N)$ . Pros: rápido. Contras: complicado de implementar.
Union-Find / truco de Arpa - responde consultas en $O(1)$ , preprocesamiento en $O(n)$ . Pros: corto, rápido. Contras: solo funciona si todas las consultas se conocen de antemano, es decir, solo admite procesamiento offline de las consultas.
Árbol cartesiano y algoritmo de Farach-Colton y Bender - responden consultas en $O(1)$ , preprocesamiento en $O(n)$ . Pros: complejidad óptima. Contras: gran cantidad de código.

Nota: el preprocesamiento es el procesamiento preliminar del arreglo dado construyendo la estructura de datos correspondiente para él.

Consulta de mínimo en un rango (Range Minimum Query)

Solución

Problemas de práctica