OIA-Wiki

Sparse Table sirve para el problema típico de “responder varias queries donde se pide el mínimo/máximo/suma de un rango”.

Sirve para problemas en donde los elementos de nuestro conjunto quedan fijos a lo largo de las queries.

La idea es guardar la respuesta que queremos de varios rangos. Los rangos que guardaremos son los que comienzan en cada elemento, y tienen como tamaño todas las potencias de $2$ posibles. Por ejemplo, si tuviéramos un vector con $5$ elementos, guardaríamos los siguientes rangos: $[0,1), [0,2), [0,4), [1,2), [1,3), [1,5), [2,3), [2,4), [3,4), [3,5), [4,5)$.

Notemos que INCLUSIVO/EXCLUSIVO.

Sea $n$ el tamaño de nuestro vector. ¿Cuántos rangos generaremos? Se puede ver que para cada elemento, habrá a lo sumo $log(n)$ rangos que comiencen en él, ya que el iésimo rango tiene tamaño $2^i$, y el máximo tamaño es $n$.

¿Cómo guardamos estos valores? Los guardaremos en un vector de $2$ dimensiones, la primera dimensión indicará el índice en el cual comienza el rango, y la segunda indicará “en qué rango estamos”. Es decir si la segunda dimensión es un $3$, estamos en el rango de tamaño $2^3$. Para guardar los valores, lo haremos con una especie de programación dinámica: comenzamos con los rangos de dimensión $1$, y a partir de ahí, para los de tamaño $2^i$ usaremos la información de los rangos de tamaño $2^{i-1}$.

Por ejemplo, si las queries fueran “el mínimo de un rango”, comenzaríamos por llenar en nuestro vector de $2$ dimensiones, $M[i][0]=v[i]$ para todo $0\Leftarrow i< n$, donde $v[i]$ tiene el elemento iésimo del vector. Y luego, $M[i][j] = min(M[i][j-1], M[i+2^{j-1}][j-1])$ para todo $i$, para cada $j$ en orden creciente.

Se ve que gracias a que INCLUSIVO/EXCLUSIVO