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 2i, 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 23. 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 2i usaremos la información de los rangos de tamaño 2i−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⇐i<n, donde v[i] tiene el elemento iésimo del vector. Y luego, M[i][j]=min(M[i][j−1],M[i+2j−1][j−1]) para todo i, para cada j en orden creciente.
Se ve que gracias a que INCLUSIVO/EXCLUSIVO