Sparse Table

Sparse Table é uma estrutura de dados que permite responder a consultas/testes de intervalo(range queries). Ela pode responder à maioria das queries de range em $O(\log n)$, mas seu verdadeiro poder é responder consultasdo mínimo no intervalo(range minimum query (RMQ) - encontrar o valor mínimo em uma sub-array de uma array) ou, equivalentemente, consultas de máximo. Para essas consultas, ele pode calcular a resposta em tempo $O(1)$.

A única desvantagem dessa estrutura de dados é que ela só pode ser usada em arrays imutáveis. Isso significa que a array não pode ser alterada entre duas consultas. Se algum elemento da array for alterado, a estrutura de dados completa deverá ser recalculada.

Intuição

Qualquer número não negativo pode ser representado exclusivamente como uma soma de potências decrescentes de $2$. Esta é apenas uma variante da representação binária de um número. Por exemplo: $13 = (1101)_2 = 8 + 4 + 1$. Para um número $x$ pode haver no máximo $\lceil \log_2 x \rceil$ números somando.

Pelo mesmo raciocínio, qualquer intervalo pode ser representado exclusivamente como uma união de intervalos com comprimentos que são potências decrescentes de dois. Por exemplo: $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$, em que o intervalo completo tem tamanho 13, e os intervalos individuais têm os tamanhos 8, 4 and 1 respectivamente. E também aqui a união consiste em no máximo $\lceil \log_2(\text{length of interval}) \rceil$ em muitos intervalos.

A idéia principal por trás das Sparse Tables é pré-calcular todas as respostas para consultas de intervalos, sendo os intervalos com tamanho de potências de $2$. Posteriormente, uma consulta de intervalo diferente pode ser respondida dividindo o intervalo em intervalos com tamanho de potência de dois, procurando as respostas pré-calculadas e combinando-as para receber uma resposta completa.

Pré-computação

Usaremos uma array 2d para armazenar as respostas para as consultas pré-calculadas. $\text{st}[i][j]$ armazenará a resposta para o intervalo $[i, i + 2^j - 1]$ de tamanho $2^j$. O tamanho da array 2d será $\text{MAXN} \times (K + 1)$, onde $\text{MAXN}$ é maior tamanho possível para a array. $\text{K}$ precisa satisfazer $\text{K} \ge \lfloor \log_2 \text{MAXN} \rfloor + 1$, pois $2^{\lfloor \log_2 \text{MAXN} \rfloor}$ é o maior tamanho de potência de $2$ que precisamos suportar. Para arrays de tamanho razoável ($\le 10^7$ elements), $K = 25$ é um bom valor.

int st[MAXN][K + 1];

Como o intervalo $[i, i + 2^j - 1]$ de tamanho $2^j$ se divide nos intervalos $[i, i + 2^{j - 1} - 1]$ e $[i + 2^{j - 1}, i + 2^j - 1]$, ambos com tamanho $2^{j - 1}$, podemos gerar a tabela eficientemente usando programação dinâmica:

for (int i = 0; i < N; i++)
    st[i][0] = f(array[i]);

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

A função $f$ dependerá do tipo da query/consulta. Para consultas de soma de intervalo, ele calculará a soma; para consultas de intervalo mínimo, calculará o mínimo.

A complexidade de tempo é $O(\text{N} \log \text{N})$.

Consultas de soma

Para esse tipo de consulta, queremos encontrar a soma de todos os valores em um intervalo. Portanto, a definição natural da função $f$ é $f(x, y) = x + y$. Podemos construir a estrutura de dados com:

long long st[MAXN][K];

for (int i = 0; i < N; i++)
    st[i][0] = array[i];

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

Para responder à consulta de soma do intervalo $[L, R]$, iteramos sobre todas as potências de dois, começando pela maior. Assim que uma potência de dois $2^j$ for menor ou igual ao comprimento do intervalo ($= R - L + 1$), processamos a primeira parte do intervalo $[L, L + 2^j - 1]$, e continuamos com o intervalo restante $[L + 2^j, R]$.

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

A complexidade de tempo para uma consulta de soma de intervalo é $O(K) = O(\log \text{MAXN})$.

Consultas mínimas de intervalo (Range Minimum Queries (RMQ))

Essas são as consultas em que a Sparse Table brilha. Ao calcular o mínimo de um intervalo, não importa se processamos um valor no intervalo uma ou duas vezes. Portanto, em vez de dividir um intervalo em vários intervalos, podemos dividir o intervalo em apenas dois intervalos sobrepostos com comprimentos de potências de $2$. Por exemplo: podemos dividir o intervalo $[1, 6]$ nos intervalos $[1, 4]$ e $[3, 6]$. O mínimo do intervalo $[1, 6]$ é claramente o mesmo mínimo do intervalo $[1, 4]$ e o mesmo mínimo do intervalo $[3, 6]$. Portanto, podemos calcular o mínimo do intervalo $[L, R]$ com:

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

Isso requer que possamos calcular $\log_2(R - L + 1)$ rápido. Você pode fazer isso pré-computando todos os logaritmos:

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

Depois disso precisamos pré-computar a estrutura da Sparse Table. Dessa vez definimos $f$ como $f(x, y) = \min(x, y)$.

int st[MAXN][K];

for (int i = 0; i < N; i++)
    st[i][0] = array[i];

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

E o mínimo de um intervalo $[L, R]$ pode ser calculado da seguinte maneira:

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

A complexidade do tempo para uma consulta de intervalo mínimo é $O(1)$.

Estruturas de dados similares que suportam mais tipos de consultas

Uma das principais fraquezas da abordagem com tempo $O(1)$ discutida na seção anterior é que essa abordagem suporta apenas consultas de funções idempotentes. Ou seja, funciona muito bem para consultas mínimas de intervalo, mas não é possível responder a consultas de soma de intervalo usando essa abordagem.

Existem estruturas de dados semelhantes que podem lidar com qualquer tipo de função associativa e responder a consultas de intervalo em $O(1)$. Uma delas é chamada Disjoint Sparse Table. A outra é a Sqrt Tree.

Problemas