Por exemplo, dado um array:
$A = {25, 30, 20, 5, 10, 35, 15}$
Podemos fazer perguntas em intervalos do array, por exemplo:
Sejam $L$ e $R$ índices de A tais que $L \leq R$
- Qual o mdc entre L e R?
- Qual o mmc entre L e R?
- Qual o menor elemento entre L e R?
- Qual o maior elemento do array inteiro?
entre outras perguntas.
Como ela funciona?
A implementação dela é similar para a maioria das operações que você escolha que ela responda. Geralmente, para mudar de uma pergunta para outra, basta mudar a operação desejada.
Vejamos seu funcionamento.
Seja $A$ um dado array de tamanho $n$ e $T$ uma Sparse Table. Como montar T dado A?
Vamos supor que T responda o menor elemento num intervalo.
Como T é uma matriz, antes de discutirmos seu número de linhas e colunas, vamos discutir o que cada casa representa, ou seja, o que significa $T[i][j]$ ?
A ideia é que cada casa $T[i][j]$ represente o menor elemento num intervalo que começa em $i$ e tem $2^j$ elementos, ou seja, $T[1][3]$ vai representar o menor elemento num intervalo que começa no índice $1$ e tem $2^3$ elementos, ou seja, do 1 até 8 (pois de 1 até 8 temos 8 elementos).
Dito isso, tiramos que T deve ter o n linhas (tamanho de A), mas e quanto ao número de colunas?
Vimos que o cada $T[i][j]$ representa um intervalo de tamanho $2^j$, mas obviamente, em algum momento, $2^j$ vai ser maior do que o tamanho do próprio A, então devemos limitar o $j$.
Buscamos a maior potência de 2 que seja menor que n.
Isso é apenas $lg(n)$.
Exemplo: se $n = 7$, $lg(7) = 2$ (arredondado para baixo).
Logo, precisamos de 3 colunas, uma para $2^0$ elementos, outra para $2^1$ e outra para $2^2$ elementos, então o número de colunas será $\lfloor lg(n) \rfloor + 1$.
A ideia é que montemos rápido essa tabela, usando casas de uma coluna anterior para gerar casas da coluna atual.
Exemplo: o menor elemento entre os índices 0 a 7 pode ser calculado usando intervalos de 0 a 3 e de 4 a 7, ou seja, usamos dois intervalos de tamanho 4 para gerar a resposta de um intervalo de tamanho 8.
Vamos ver isso na prática:
$A = {25, 30, 20, 5, 10, 35, 15}$
Linhas de $T = ||A|| = 7$;
Colunas de $T = \lfloor lg(||A||) \rfloor + 1 = 2 + 1 = 3$
Preenchemos T com um valor que nunca será alcançado, por exemplo, -1 nesse caso.
T inicialmente será:
Os intervalos na coluna 0, ou seja, de tamanho $2^0 = 1$, obviamente, para cada linha, representam os próprios elementos, isto é, $T[i][0]$ é o mínimo entre o intervalo partindo do índice $i$ (de A) com tamanho 1, ou seja, $A[i]$.
Na coluna 1, os intervalos tem tamanho 2. Podemos calcular $T[i][1]$ como o mínimo entre a casa $i$ da coluna anterior e a casa $i + 2^(j-1)$ da coluna anterior.
Exemplo: $T[2][1] = min(T[2][0], \; T[2 + 2^{1-1}][0]) = min(T[2][0], \; T[3][0]) = 5$
A ideia é calcular o mínimo de um intervalo de tamanho $k$ usando os dois intervalos pré-calculados de tamanho $\frac{k}{2}$ que cobrem todo o intervalo desejado, por exemplo, de 2 até 3, podemos calcular através do mínimo entre só o 2 e só o 3, que são intervalos da metade do tamanho e, juntos, encobrem todo o intervalo desejado.
Note que não calculamos o último valor pelo fato de não haver um intervalo de tamanho 2 partindo do índice 6.
Para calcular a coluna 2, usamos os valores pré-calculados da coluna 1.
Exemplo: $T[0][2]$ representa o mínimo entre 0,1,2 e 3. Podemos calcular isso pelo mínimo entre o intervalo 0,1 e o intervalo 2,3. Já temos esse intervalo calculado.
$T[0][2] = min(T[0][1], \; T[0 + 2^{2-1}][1]) = min(T[0][1], \; T[2][1]) = 5$
Paramos de calcular no índice 3 porque não existe intervalo de tamanho 4 partindo do índice 4.
Essa é nossa Sparse Table para o array A e operação de mínimo.
E como saber, por exemplo, o mínimo entre 2 e 4 (um intervalo de tamanho 3) ?
Para fazer uma pergunta sobre um intervalo, devemos primeiramente saber de quantos elementos estamos falando.
A coluna que vamos olhar na pesquisa do intervalo $L$ até $R$ é $\lfloor lg(R-L+1) \rfloor$ (que representa a maior potência de 2 menor que o tamanho do intervalo dado).
Entre 2 e 4 há 4-2+1 elementos, ou seja, 3.
Logo, tiramos que não podemos procurar em intervalos de tamanho 4, por exemplo, pois iríamos incluir elementos a mais na nossa busca.
Se procurássemos no mínimo de tamanho 4 partindo do elemento 2, iríamos olhar 2,3,4 e 5, e talvez a resposta seja o 5, gerando um erro.
O jeito é olharmos os intervalos imediatamente menores que o nosso, ou seja, de tamanho 2.
Também não olhamos intervalos consecutivos, por exemplo, $a \text{ até }b$, $b+1 \text{ até } c$, pois isso gera erro, (2 até 7, tamanho 6, olhando coluna 2, 2 até 5, 6 até 9, inclui 8 e 9 que não deviam ser olhados).
A solução é intercalar a busca:
Seja $A = {4,8,5,2,7,1}$
A Sparse Table $T$ será:
Vamos realizar uma busca entre 2 e 4.
$\lfloor lg(4-2+1) \rfloor = 1$.
Devemos procurar na coluna 1. Sabemos de cara que, partindo do índice 2, pelo menos 2 posições à frente estão garantidamente incluídas no intervalo. Podemos olhar $T[2][1]$ para termos a resposta entre os índices 2 e 3. Mas e o resto do intervalo?
Sabemos que ele acaba no 4. Podemos pegar o intervalo de tamanho máximo possível cujo último elemento seja o 4, isso é, o tamanho máximo é 2 (pois 4 já é maior que o tamanho do intervalo), e o intervalo de tamanho 2 cujo último elemento é o 4 é do 3 ao 4.
0
1
/ 2
\ 3 \
4 /
5
Nossos intervalos geraram uma intersecção de um elemento (o índice 3), mas como queremos o mínimo num intervalo, isso não importa (se fosse a soma dos elementos, por exemplo, contar o 3 duas vezes geraria erro).
Concluindo, a busca pelo mínimo num intervalo $L$ até $R$ de tamanho $n$ é o mínimo entre:
- intervalo começando em $L$ de tamanho $\lfloor lg(n) \rfloor$;
- intervalo começando em $L+(R - 2^{\lfloor lg(n) \rfloor})$ de tamanho $\lfloor lg(n) \rfloor$.
int A[100]; //array original int T[100][7]; //sparse table //7 = floor(log2(100)) + 1 //l e c representam os limites da linha //e da coluna onde T vai ser preenchida //no caso, se passa em l o tamanho atual de A //e em c, floor(log2( ||A|| )) + 1
#define OP min
void build(int l, int c){ memset(T, -1, sizeof(T)); for(int i = 0; i < l; i++) T[i][0] = A[i]; int p = 1, lim; for(int j = 1; j < c; j++){ p <<= 1; lim = l - p + 1; for(int i = 0; i < lim; i++) T[i][j] = OP(T[i][j-1], T[i + (p>>1)][j-1]); } } int lookup(int l, int r){ int num = r - l + 1; int col = floor(log2(num)); return OP(T[l][col], T[l + num - (1<<col)][col]); }
Note que usamos um #define para dizer que a operação realizada pela Sparse Table será o mínimo nos intervalos. Poderíamos usar max, mdc, mmc, entre outras funções.
Complexidade de Criação:
Espaço e Tempo = O(n lg(n))
Complexidade de Pergunta: O(1)
Nenhum comentário:
Postar um comentário