RMQ y Sparse Table

Enviado por fmoreno el Lun, 23/09/2019 - 13:38

Consideremos el siguiente problema: tenemos una sequencia $a_1, a_2, \ldots, a_n$ de números y se nos pide calcular el mínimo valor que toma la secuencia entre el $L$-ésimo elemento y el $R$-ésimo elemento, para varios pares $(L, R)$. Este problema se conoce como Range Minimum Query (RMQ) y aparece en el desarrollo de otros algoritmos, por ejemplo en el algoritmo para encontrar el primer ancestro común de dos nodos de un árbol.

La solución más sencilla es para cada par $(L, R)$ iterar desde el $L$-ésimo elemento hasta el $R$-ésimo y encontrar el mínimo directamente. Sin embargo, si tenemos muchas consultas $(L, R)$ que responder esto no es eficiente, porque cada consulta se responde en $\mathcal{O}(n)$. En este manual vamos a tratar de dar una solución al problema que responda cada consulta en $\mathcal{O}(1)$. Para ello tendremos que hacer una precomputación, es decir, tendremos que hacer unos cálculos previos que permitan hacer más eficiente la respuesta de consultas sea (si no, obviamente, no es posible responder en $\mathcal{O}(1)$: al menos se necesita $\mathcal{O}(n)$ de tiempo para procesar todos los elementos).

Una forma brusca de hacer esto es precalcular el resultado para todos los intervalos $(L, R)$: así, para responder una consulta sólo tenemos que consultar el resultado que ya hemos calculado. Hay un total de $\mathcal{O}(n^2)$ intervalos y cada intervalo tiene longitud promedio $\mathcal{O}(n)$, así que en un principio este método usaría $\mathcal{O}(n^3)$ de tiempo de precomputación. Por supuesto, es fácilmente mejorable a $\mathcal{O}(n^2)$ si se aprovechan resultados calculados anteriormente: por ejemplo, el valor correspondiente al intervalo $[L, R+1]$ se puede calcular en $\mathcal{O}(1)$ si ya se tiene el valor del intervalo $[L, R]$.

Este método puede ser útil si $n$ es suficientemente pequeño, pero se puede intuir que es mejorable: si solo nos van a preguntar por algunos intervalos y no por todos, tener todos los resultados precomputados parece demasiado. De hecho, la idea clave es que para poder responder una consulta de cualquier intervalo eficientemente no es necesario tener todos los intervalos precomputados, sino solo algunos. En concreto, si cualquier intervalo puede expresarse como la unión de dos intervalos cuyo mínimo tenemos precomputado (es decir, que con esos dos intervalos precomputados “cubrimos” el intervalo), podemos retornar el mínimo de los dos valores.

La solución conocida por el nombre de Sparse Table consiste en precomputar todos los intervalos de longitud igual a una potencia de $2$. Se puede ver que cualquier intervalo $[L, R]$ se puede cubrir por dos intervalos con longitud potencia de $2$: se coge el intervalo más largo que empiece en L y esté contenido en $[L, R]$ y el más largo que acabe en R y esté contenido en $[L, R]$: como cada uno de estos dos intervalos cubre al menos la mitad del intervalo total, el intervalo queda completamente cubierto. El número de intervalos de longitud potencia de $2$ totales es $\mathcal{O}(n \log n)$ y el tiempo de precálculo es $\mathcal{O}(n \log n)$ también, ya que los valores para los intervalos de longitud $2^{i+1}$ se obtienen de los dos de longitud $2^i$ que cubren.

 

Una posible implementación es la siguiente: (Téngase en cuenta que 1<<j $\equiv 2^j$)

//st es un vector<vector<int>> de dimensiones n x log n
//st[i][j] contiene el índice del menor elemento en el intervalo [i, i+2^j-1]

//Precomputación:
for(int i=0; i < n; ++i) st[i][0] = i; //los intervalos de longitud 1 solo tienen un elemento

for(int j=1; (1<<j) <= n; ++j) { //vamos iterando de menor a mayor longitud
    for(int i=0; i+((1<<j)-1) < n; ++i) {
        int m1 = st[i][j-1];
        int m2 = st[i+(1<<(j-1))][j-1];
        //m1 y m2 son los índices de los menores elementos de los dos intervalos cuya unión es el intervalo [i, i+2^j-1]
        if(a[m2] < a[m1]) st[i][j] = m2;
        else st[i][j] = m1;
    }
}

//Función que devuelve el índice del menor elemento en [i, j]:
int rmq(int i, int j) {
    int k = 0;
    while(1<<(k+1) <= j-i+1) ++k;
    int m1 = st[i][k];
    int m2 = st[j-(1<<k)+1][k];
    if(a[m2] < a[m1]) return m2;
    else return m1;
}

 

(Nótese que el bucle while para calcular k hace que la complejidad de cada consulta sea $\mathcal{O}(\log n)$, pero con constante muy baja. Para conseguir un $\mathcal{O}(1)$ verdadero se pueden precomputar los logaritmos de 1 a n).

 

La Sparse Table tal como la hemos presentado aquí, a diferencia de otras estructuras de datos más generales como el Segment Tree, tiene casi como única finalidad resolver el problema de RMQ. La razón es que si, por ejemplo, quisiéramos utilizar la misma idea para resolver el problema de RSQ (Range Sum Query, es decir, la suma de números en un intervalo), no funcionaría lo de que el resultado se pueda calcular a partir de dos intervalos que cubran el intervalo completo, porque si los dos intervalos se intersecan hay términos que sumamos dos veces. Aquí hemos aprovechado la “idempotencia” de la función $\min$, es decir, que da igual que algunos términos los consideres dos veces porque el mínimo es igual. La versión general de la Sparse Table utiliza que cualquier intervalo se puede expresar como unión disjunta de varios intervalos de longitud potencia de dos: esta versión permite calcular la RSQ y en general cualquier tipo de consultas sobre operaciones binarias asociativas sobre un intervalo, pero al no haber un número constante de intervalos precomputados en cada consulta la complejidad ya no es $\mathcal{O}(1)$, sino $\mathcal{O}(\log n)$. El lector interesado puede pensar los detalles de la implementación de esta versión. En el manual de Árboles de Segmentos / Segment trees explicamos una estructura de datos diferente que además de hacer consultas de cualquier operación binaria asociativa en un intervalo también en $\mathcal{O}(\log n)$, (y sólo utilizando $\mathcal{O}(n)$ de memoria, frente a la $\mathcal{O}(n \log n)$ que usa la Sparse Table) también admite otras funcionalidades, como por ejemplo la actualización de la secuencia sobre la que se está trabajando.

Printer Friendly, PDF & Email

Añadir nuevo comentario

Texto sin formato

  • No se permiten etiquetas HTML.
  • Saltos automáticos de líneas y de párrafos.
  • Las direcciones de correos electrónicos y páginas web se convierten en enlaces automáticamente.