Resolver RMQ (consulta de mínimo en un rango) encontrando el LCA (ancestro común más bajo)

Se da un arreglo A[0..N-1]. Para cada consulta de la forma [L, R] queremos encontrar el mínimo en el arreglo A desde la posición L hasta la posición R. Asumiremos que el arreglo A no cambia en el proceso, es decir, este artículo describe una solución al problema de RMQ estático.

Aquí hay una descripción de una solución asintóticamente óptima. Se aparta de las demás soluciones del problema de RMQ, ya que es muy distinta de ellas: reduce el problema de RMQ al problema de LCA, y luego usa el algoritmo de Farach-Colton y Bender, que reduce el problema de LCA de vuelta a un problema de RMQ especializado y lo resuelve.

Algoritmo

Construimos un árbol cartesiano a partir del arreglo A. Un árbol cartesiano de un arreglo A es un árbol binario con la propiedad de min-heap (el valor del nodo padre tiene que ser menor o igual que el valor de sus hijos) tal que el recorrido inorden del árbol visita los nodos en el mismo orden en que están en el arreglo A.

En otras palabras, un árbol cartesiano es una estructura de datos recursiva. El arreglo A se partirá en 3 partes: el prefijo del arreglo hasta el mínimo, el mínimo, y el sufijo restante. La raíz del árbol será un nodo correspondiente al elemento mínimo del arreglo A, el subárbol izquierdo será el árbol cartesiano del prefijo, y el subárbol derecho será un árbol cartesiano del sufijo.

En la siguiente imagen se puede ver un arreglo de longitud 10 y el árbol cartesiano correspondiente.

La consulta de mínimo en un rango [l, r] es equivalente a la consulta de ancestro común más bajo [l', r'], donde l' es el nodo correspondiente al elemento A[l] y r' el nodo correspondiente al elemento A[r]. En efecto, el nodo correspondiente al elemento más pequeño del rango tiene que ser un ancestro de todos los nodos del rango, por tanto también de l' y r'. Esto se sigue automáticamente de la propiedad de min-heap. Y también tiene que ser el ancestro más bajo, porque de lo contrario l' y r' estarían ambos en el subárbol izquierdo o ambos en el derecho, lo que genera una contradicción ya que en tal caso el mínimo ni siquiera estaría en el rango.

En la siguiente imagen se pueden ver las consultas de LCA para las consultas de RMQ [1, 3] y [5, 9]. En la primera consulta el LCA de los nodos A[1] y A[3] es el nodo correspondiente a A[2], que tiene el valor 2, y en la segunda consulta el LCA de A[5] y A[9] es el nodo correspondiente a A[8], que tiene el valor 3.

Tal árbol se puede construir en tiempo $O(N)$ y el algoritmo de Farach-Colton y Bender puede preprocesar el árbol en $O(N)$ y encontrar el LCA en $O(1)$.

Construcción de un árbol cartesiano

Construiremos el árbol cartesiano agregando los elementos uno tras otro. En cada paso mantenemos un árbol cartesiano válido de todos los elementos procesados. Es fácil ver que agregar un elemento s[i] solo puede cambiar los nodos del camino más a la derecha — empezando en la raíz y tomando repetidamente el hijo derecho — del árbol. El subárbol del nodo con el valor más pequeño, pero mayor o igual que s[i], se convierte en el subárbol izquierdo de s[i], y el árbol con raíz s[i] se convertirá en el nuevo subárbol derecho del nodo con el valor más grande, pero menor que s[i].

Esto se puede implementar usando una pila para guardar los índices de los nodos más a la derecha.

vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!s.empty() && A[s.top()] >= A[i]) {
        last = s.top();
        s.pop();
    }
    if (!s.empty())
        parent[i] = s.top();
    if (last >= 0)
        parent[last] = i;
    s.push(i);
}