Tabla Dispersa (Sparse Table)

La Tabla Dispersa (Sparse Table) es una estructura de datos que permite responder consultas de rango. Puede responder la mayoría de las consultas de rango en $O(\log n)$ , pero su verdadero poder es responder consultas de mínimo en un rango (o las equivalentes de máximo). Para esas consultas puede calcular la respuesta en $O(1)$ .

El único inconveniente de esta estructura es que solo se puede usar sobre arreglos inmutables. Eso significa que el arreglo no puede cambiar entre dos consultas. Si cualquier elemento del arreglo cambia, hay que recomputar la estructura completa.

Intuición

Cualquier número no negativo se puede representar de forma única como una suma de potencias de dos decrecientes. Esto es solo una variante de la representación binaria de un número. P. ej. $13 = (1101)_2 = 8 + 4 + 1$ . Para un número $x$ puede haber a lo sumo $\lceil \log_2 x \rceil$ sumandos.

Por el mismo razonamiento, cualquier intervalo se puede representar de forma única como unión de intervalos con longitudes que son potencias de dos decrecientes. P. ej. $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$ , donde el intervalo completo tiene longitud 13, y los intervalos individuales tienen longitudes 8, 4 y 1 respectivamente. Y también acá la unión consiste de a lo sumo $\lceil \log_2(\text{length of interval}) \rceil$ intervalos.

La idea principal detrás de las Tablas Dispersas es precomputar todas las respuestas para consultas de rango con longitud potencia de dos. Después, una consulta de rango distinta se puede responder partiendo el rango en rangos de longitudes potencia de dos, consultando las respuestas precomputadas y combinándolas para obtener una respuesta completa.

Precomputación

Usaremos un arreglo bidimensional para guardar las respuestas de las consultas precomputadas. $\text{st}[i][j]$ guardará la respuesta para el rango $[j, j + 2^i - 1]$ de longitud $2^i$ . El tamaño del arreglo bidimensional será $(K + 1) \times \text{MAXN}$ , donde $\text{MAXN}$ es la mayor longitud posible del arreglo. $\text{K}$ tiene que cumplir $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor$ , porque $2^{\lfloor \log_2 \text{MAXN} \rfloor}$ es el mayor rango de longitud potencia de dos que tenemos que soportar. Para arreglos de longitud razonable ( $\le 10^7$ elementos), $K = 25$ es un buen valor.

La dimensión $\text{MAXN}$ va segunda para permitir accesos a memoria consecutivos (amigables con la caché).


int st[K + 1][MAXN];

Como el rango $[j, j + 2^i - 1]$ de longitud $2^i$ se parte bien en los rangos $[j, j + 2^{i - 1} - 1]$ y $[j + 2^{i - 1}, j + 2^i - 1]$ , ambos de longitud $2^{i - 1}$ , podemos generar la tabla de forma eficiente usando programación dinámica:


std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

La función $f$ dependerá del tipo de consulta. Para consultas de suma en un rango calculará la suma; para consultas de mínimo, el mínimo.

La complejidad temporal de la precomputación es $O(\text{N} \log \text{N})$ .

Consultas de suma en un rango

Para este tipo de consultas queremos encontrar la suma de todos los valores en un rango. Por lo tanto, la definición natural de la función $f$ es $f(x, y) = x + y$ . Podemos construir la estructura de datos con:


long long st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

Para responder la consulta de suma del rango $[L, R]$ , iteramos sobre todas las potencias de dos, empezando por la más grande. En cuanto una potencia de dos $2^i$ es menor o igual que la longitud del rango ( $= R - L + 1$ ), procesamos la primera parte del rango $[L, L + 2^i - 1]$ y continuamos con el rango restante $[L + 2^i, R]$ .


long long sum = 0;
for (int i = K; i >= 0; i--) {
    if ((1 << i) <= R - L + 1) {
        sum += st[i][L];
        L += 1 << i;
    }
}

La complejidad temporal de una consulta de suma en un rango es $O(K) = O(\log \text{MAXN})$ .

Consultas de mínimo en un rango (RMQ)

Estas son las consultas donde la Tabla Dispersa brilla. Al computar el mínimo de un rango, no importa si procesamos un valor del rango una vez o dos. Por lo tanto, en lugar de partir un rango en varios rangos, también podemos partirlo en solo dos rangos superpuestos de longitud potencia de dos. P. ej. podemos partir el rango $[1, 6]$ en los rangos $[1, 4]$ y $[3, 6]$ . El mínimo del rango $[1, 6]$ es claramente el mismo que el mínimo del mínimo de $[1, 4]$ y el mínimo de $[3, 6]$ . Así que podemos computar el mínimo del rango $[L, R]$ con:

$\min(\text{st}[i][L], \text{st}[i][R - 2^i + 1]) \quad \text{ where } i = \log_2(R - L + 1)$

Esto requiere que podamos computar $\log_2(R - L + 1)$ rápido. Se puede lograr precomputando todos los logaritmos:


int lg[MAXN+1];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i/2] + 1;

Como alternativa, el log se puede computar al vuelo en espacio y tiempo constantes:


// C++20
#include <bit>
int log2_floor(unsigned long i) {
    return std::bit_width(i) - 1;
}
 
// pre C++20
int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

Este benchmark muestra que usar el arreglo lg es más lento por cache misses.

Después hay que precomputar la estructura Sparse Table. Esta vez definimos $f$ como $f(x, y) = \min(x, y)$ .


int st[K + 1][MAXN];

std::copy(array.begin(), array.end(), st[0]);

for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Y el mínimo de un rango $[L, R]$ se puede computar con:


int i = lg[R - L + 1];
int minimum = min(st[i][L], st[i][R - (1 << i) + 1]);

La complejidad temporal de una consulta de mínimo en un rango es $O(1)$ .

Estructuras de datos similares que soportan más tipos de consultas

Una de las principales debilidades del enfoque $O(1)$ de la sección anterior es que solo soporta consultas de funciones idempotentes . Es decir, funciona muy bien para consultas de mínimo, pero no es posible responder consultas de suma en un rango con este enfoque.

Hay estructuras de datos similares que pueden manejar cualquier tipo de función asociativa y responder consultas de rango en $O(1)$ . Una de ellas se llama Disjoint Sparse Table . Otra sería el Árbol Sqrt.