Sempre me surpreendo com a sagacidade das pessoas que inventaram algumas estruturas de dados e algoritmos. Essa é uma das estruturas de dados que eu me surpreenderam com a sua beleza :-)
Você pode encontrar maiores detalhes sobre como o RMQ utilizando uma sparse table foi utilizado para resolver o problema de Lowest Common Ancestor nesse artigo: Bender, Michael A., and Martin Farach-Colton. "The LCA problem revisited." LATIN 2000: Theoretical Informatics. Springer Berlin Heidelberg, 2000. 88-94.
Essa estrutura é muito utilizada para implementar o Lowest Common Ancestor.
Agora, vamos ao que interessa. A ideia é encontrar o elemento mínimo de um determinado intervalo do array. Nesse caso, iremos fazer essa consulta em O(1).
Para isso, teremos que constuir uma estrutura de uma matriz, que nos custará O(n log(n)).
Se os elementos do array mudarem com frequência é melhor você utilizar uma Segment Tree, pois nesse caso, uma alteração em um dos elementos dessa Sparse Table requer reconstruir toda a matriz (n log(n)), já em uma segment tree essa operação custa O(log(n)).
Como sempre, vamos começar com um exemplo. Suponha o seguinte array:
a = [5, 3, 2, 8, 1, 4]
Seja n o número de elementos. Logo, nesse caso, n=6.
Iremos construir uma matriz cuja a linha indica qual o índice inicial do array e a coluna indica o tamanho da subsequência. Só que esse tamanho será sempre uma potência de 2. Suponha que chamamos a nossa matriz de spt (sparse table). Logo, a célula spt[0][0] significa o índice inicial do array 0 e com tamanho da subsequência 2^0 = 1. Ou seja, essa célula guardará o menor valor de apenas um elemento, que nesse caso é o 0.
Já a célula spt[0][1] guarda o menor valor do índice começando em 0 e com tamanho 2^1 = 2. Ou seja, ela guarda o menor valor da subsequência { a[0], a[1] }.
Assim, uma matriz que tenha a célula spt[8][3] guardará o valor da subsequência { a[8] ... a[15] } , ou seja, iniciando em a[8] com tamanho 2^3 = 8.
Sendo assim, vamos primeiro aprender a constuir a matriz e depois explicaremos como consultar.
Começamos preenchendo as colunas. No nosso exemplo, como tempos n=6, precisaremos de n linhas na nossa matriz.
Todos os valores de spt[i][0] , i <=0 < n, significam sequências começando em i e com tamanho 1. Ou seja, elas representam os próprios elementos do array. Assim, a sua matriz começará assim:
0 1 2
----|----|----|
0 [ 5 , -1, -1 ]
1 [ 3 , -1, -1 ]
2 [ 2 , -1, -1 ]
3 [ 8 , -1, -1 ]
4 [ 1 , -1, -1 ]
5 [ 4 , -1, -1 ]
Precisaremos de round_up(log (n)) colunas. Nesse caso, log(6) = 2,58, então utilizaremos 3 colunas.
A partir de agora, as outras células da matriz serão preenchidas usando os valores que já calculamos antes.
spt[0][1], significa o menor valor do array começando em 0 e com tamanho 2^1=2. Podemos pensar também que se quebrarmos esse intervalo de spt[0][1] ao meio, spt[0][1] será o menor valor do dois intervalos que foram quebrados.
spt[0][1] = menor( spt[0][0] , spt[1][0] )
Como já calculamos os valores de todos os intervalos de tamanho 1, podemos preencher a tabela usando a lógica acima.
spt[0][1] = menor( spt[0][0] , spt[1][0] )
spt[1][1] = menor( spt[1][0] , spt[2][0] )
spt[2][1] = menor( spt[2][0] , spt[3][0] )
spt[3][1] = menor( spt[3][0] , spt[4][0] )
spt[4][1] = menor( spt[4][0] , spt[5][0] )
Com isso, a tabela ficará:
0 1 2
----|----|----|
0 [ 5 , 3, -1 ]
1 [ 3 , 2, -1 ]
2 [ 2 , 2, -1 ]
3 [ 8 , 1, -1 ]
4 [ 1 , 1, -1 ]
5 [ 4 , -1, -1 ]
Perceba que não preenchemos a posição spt[5][1], porque a partir do índice 5, não existem dois elementos, pois 5 é o último índice do array.
Repetimos esse processo, agora com um intervalo maior.
spt[0][2], guardará o maior valor do intervalo que começa no índice 0 e tem tamanho 4. Isso compreende os elementos de índice do array 0,1,2,3. Podemos dividir esse intervalo no meio e fazemos:
spt[0][2] = menor ( intervalo começando em 0 com tamanho 2, intervalo começando em 2 com tamanho 2)
spt[0][2] = menor ( spt[0][1], spt[2][1] )
Mais uma vez, já temos todos os intervalos de tamanho 2 calculados, logo, podemos preencher a matriz facilmente:
spt[0][2] = menor( spt[0][1] , spt[2][1] )
spt[1][2] = menor( spt[1][1] , spt[3][1] )
spt[2][2] = menor( spt[2][1] , spt[4][1] )
Perceba que não preenchemos as outras linhas dessa coluna, pois o último intervalo usado spt[4][1] já contemplou o último elemento.
Com isso, a tabela final ficará:
0 1 2
----|----|----|
0 [ 5 , 3, 2 ]
1 [ 3 , 2, 1 ]
2 [ 2 , 2, 1 ]
3 [ 8 , 1, -1 ]
4 [ 1 , 1, -1 ]
5 [ 4 , -1, -1 ]
Perceba que para contruir a matriz gasteremos O(n log(n) ). Além disso, também precisamos de n log(n) de memória.
Nós construímos a árvore, guardando sempre os menores valores em intervalos que são potência de 2. Assim, para consultar o menor valor de um intervalo precisamos descobrir, dado o intervalo de consulta, em que células da matriz aquele intervalo está contido.
Suponha primeiro o caso mais fácil, onde queremos saber um intervalo que "casa" exatamente com uma única célula da matriz.
Por exemplo, suponha que a consulta é rmq(2,5). OU seja, quero saber o menor valor entre os elementos { a[2], a[3], a[4], a[5] }.
A primeira coisa a descobrir é o tamanho (length) do intervalo desejado. Nesse caso, o length = 4.
Como construímos a matriz em potências de 2, a coluna será dada pela função inversa da potência, que é a logarítmica.
k = arredondar_para_baixo( log2 (4) ) = 2
Nesse caso, já temos na tabela exatamente o intervalo que começa em 2 e com tamanho 4 (coluna k): spt[2][2]
Ou seja, o menor valor desse intervalo é o 1.
Suponha agora que a consulta é:
rsq(0,5). Nesse caso, queremos saber qual o menor elemento do intervalo { a[0], a[1], a[2], a[3], a[4], a[5] }
Não temos nenhuma célula da tabela que guarda essa informação diretamente.
Entretanto, se quebrarmos esse intervalo em intervalos menores, podemos pensar em:
intervalo 1 : começo em 0, tamanho 4 = { a[0], a[1], a[2], a[3] }
intervalo 2: começo em 2, tamanho 4 = { a[2], a[3], a[4], a[5] }
Perceba que esses dois intervalos possuem elementos repetidos, mas se você fizer a união desses dois conjuntos obterá exatamente o conjunto desejado.
Como estamos querendo saber o valor mínimo, o valor mínimo será o mínimo desses dois conjuntos.
Mas esses dois conjuntos a gente já tem calculado na tabela, eles são:
intervalo 1: spt[0][2]
intervalo2: spt[2][2]
logo a resposta será o min( spt[0][2], spt[2][2] ) = 1
Bem, agora nos resta saber como que a partir do intervalo desejado, encontramos esses dois subintervalos.
A sacada é a seguinte, sempre iremos dividir em dois intervalos, de acordo com a seguinte fórmula:
intervalo 1: spt[ i ][ k ]
intervalo 2: spt[ j - 2^k + 1 ][ k ]
Quando o length é uma potência de 2, o seu logaritmo dará um número exato. Portanto, k não terá sido arredondado, e portanto, quando pegamos o final do intervalo desejado, e subtraímos do seu tamanho (lembrando que tamanho, length, é igual a 2^k), obtemos exatamente o início do intervalo), ou seja, o intervalo 1 será igual ao 2. (O +1 está aqui pq o tamanho é sempre j - i +1 )
Veja por exemplo como esses intervalos ficariam no primeiro caso:
rmq(2,5)
i = 2
j = 5
length = 5 - 2 +1 = 4
k = log2(length) = 2 (não precisou arrendondar para baixo, 4 é múltiplo de 2)
intervalo 1: spt[ 2 ][ 2 ]
intervalo 2: spt[5 - 2^2 + 1][ 2 ] = spt[ 2 ][ 2 ]
Ou ainda essa outra consulta com intervalo também múltiplo de 2:
rmq(0,3)
i = 0
j = 3
length = 4
k = 2
intervalo 1: spt[ 0 ][ 2 ]
intervalo 2: spt[ 3 - 4 + 1 ][ 2 ] = spt[ 0 ][ 2 ]
Entretanto, quando length não é uma potência de 2, então precisamos dos dois intervalos realmente. Veja por exemplo:
rmq(0,5)
i = 0
j = 5
length = 6
k = log2(6) = 2.58 = arredondando para baixo = 2
intervalo 1: spt[ 0 ][ 2 ]
intervalo 2: spt[ 5 - 4 + 1 ][ 2 ] = spt[ 2 ][ 2 ]
Nesse caso, perceba que foram dois intervalos diferentes, cada um com tamanho 4. Mesmo com sobreposição, a união deles é exatamente o conjunto desejado. Basta agora retornar o mínimo dos 2.
Com essa conta e, portanto, em O(1) você consegue recuperar o mínimo de qualquer intervalo do array.
/*Sparse TableRodrigo PaesRMQ - Range Minimal Query sem atualização!Caso os valores do array precisem ser atualizados, segment tree.Para fazer 2^x , estamos fazendo: 1 << x, ou seja, deslocamos o 1 x vezes para à esquerda*/#include <bits/stdc++.h>using namespace std;#define N 1000#define M 10 // Log2(N) .. nesse caso, 2^10 = 1024, portanto, suficiente para 1000int a[N]; // list of elementsint spt[N][M]; //sparse tableint n;/*Constrói uma matriz esparsa usando DP.Uma posição spt[i][j] representa o índice do array a com menor valor no intervalo [i, 2^j]Por exemplo, spt[12,4], guarda o menor elemento começando entre a[12] e a[12+2^4],ou seja,a[12] e a[28]intervalo fechado nos dois lados.O( n log(n) )*/void build(){ /* A tabela é preechida coluna por coluna. Primeiro os casos base. Depois todos os intervalos de tamanho 1, depois 2, 4, 8, 16 e assim por diante. Por exemplo: o array: [18, 17, 13, 5, 15, 11, 20] [ * * * * * * * * * * * * * * * * * * * * * ] passo 1: preencherá com os casos base (j=0) , tamanho 1, pois 2^0 = 1 [ 0 * * 1 * * 2 * * 3 * * 4 * * 5 * * 6 * * ] passo 2: intervalos com tamanho 2 (j=1, 2^1 =2) para saber quanto é o valor de spt[0][1], perceba que já calculamos os intervalos [0][0] e [1][0] no caso base. Ou seja, o spt[0][1], representa o menor valor do array iniciando na posição 0 e com tamanho 2, ou seja, o menor valor entre 18 e 17. Logo, spt[0][1] = índice do mínimo entre ( a[ spt[0][0] ], a[ spt[1,0] ] ) A mesma coisa para saber [1][1]. Nesse caso: spt[1][1] = índice do mínimo entre ( a[ spt[1][0] ], a[ spt[2,0] ] ) Veja que é como se estivemos fazendo: spt[0][1] = índice do mínimo entre [ (18, 17), 13 , 5, 15, 11, 20] spt[1][1] = índice do mínimo entre [18, ( 17, 13 ) , 5, 15, 11, 20] spt[2][1] = índice do mínimo entre [18, 17, (13 , 5), 15, 11, 20] ... spt[5][1] = índice do mínimo entre [18, 17, 13 , 5, 15, (11, 20)] [ 0 1 * 1 2 * 2 3 * 3 3 * 4 5 * 5 5 * 6 * * ] passo 3: agora precisamos calcular com intervalos de tamanho 4 (j=2, 2^2=4) Primeiro, precisamos calcular spt[0][2]. [(18, 17, 13, 5), 15, 11, 20] Nesse caso, já calculamos (0,1) e também (2,1). Vamos sempre guardar os valores mínimos em potências de 2. Ou seja, já temos: [(18, 17), 13, 5, 15, 11, 20], armazenado em spt[0][1] [18, 17, (13, 5), 15, 11, 20], armazenado em spt[2][1] Assim, para saber o valor de spt[0][2] , basta pegar o mínimo entre spt[0][1] e spt[2][1] Agora precisamos calcular spt[1][2]: [18, (17, 13, 5, 15), 11, 20] Mais uma vez, dividmos o intervalo no meio e pegamos para obter: [18, (17, 13), 5, 15, 11, 20], já armazenado em spt[1][1] [18, 17, 13, (5, 15), 11, 20], já armazenado em spt[3][1] Assim, preencheremos a nossa tabela: [ 0 1 3 1 2 3 2 3 3 3 3 3 4 5 * 5 5 * 6 * * ] */ /* 2^j <= n */ for (int j = 0; (1 <<j) <= n; ++j) { /* Como i denota o início do intervalo e 2^j o tamanho dele O valor da soma do inicio mais o seu tamanho não pode ultrapassar o tamanho do array. */ for (int i=0; (i + (1<< j) - 1) < n; ++i) { if (j) //se não é zero { /* Como cada j representa um intervalo de 2^j, quando diminuímos um do j, pegamos o intervalo anterior, ou seja, uma potência de 2 a menos. O i marca a posição inicial do array */ int pos1 = spt[i][j-1]; /* Esse calculo da linha na matriz marca a metade do intervalo. Ou seja, o i + o deslocamento da metade do tamanho do conjunto que esse j representa. */ int pos2 = spt[i + (1<<(j-1))][j-1]; spt[i][j] = a[pos1] < a[pos2] ? pos1 : pos2; } else { /* caso base: a primeira coluna da matriz tem intervalo tamanho zero. e portanto, o menor elemento é ele mesmo. por exemplo: spt[3][0] receberá 3 */ spt[i][j] = i; } } }}/*Retorna o índice do menor elemento.i = índice inicial do intervalo (inclusivo)j = índice inicial do intervalo (inclusivo)O(1)*/int rmq(int i, int j){ int length = j-i +1; /* 2^k <= length Como cada coluna da matriz guarda o menor elemento dos intervalos que são potência de 2, sabendo o tamanho do intervalo, usamos a função inversa da potência para encontrar a coluna da matriz. Por exemplo, suponha que i=0, j=2, logo intervalo tem tamanho 3 (2-0+1) Nesse caso, bastam dois conjuntos de tamanho 2 sobrepostos para entrar o resultado. Se considerarmos o array acima, então teríamos: conjunto 1: [(18, 17), 13, 5, 15, 11, 20] , spt[0][1] conjunto 2: [18, (17, 13), 5, 15, 11, 20], spt[1][1] Se soubermos o mínimo desses 2 conjuntos, saberemos o mínimo de i,j Perceba que a sobreposição não nos traz problemas, uma vez que queremos o mínimo. Já no caso onde os valores fossem i=0, j=3, teríamos o tamanho 4. Nesse caso, k seria igual a 2. E portanto, os intervalos teríam 2^2 elementos, ou seja, 4. Na tabela já temos esse valor calculado: conjunto 1: [(18, 17, 13, 5), 15, 11, 20] , spt[0][2] Perceba que no nosso cálculo, isso já é considerado, pois o if ficará: a[ spt[0][2] ] <= a[ spt[0][2] ], ou seja, os mesmos valores. O último cenário ocorreria no caso i=0, j=4: [(18, 17, 13, 5, 15), 11, 20] k seria igual a 2 e portanto precisaremos de novo de uma sobreposição, nesse caso, calculada como: conjunto 1: [(18, 17, 13, 5), 15, 11, 20] , spt[0][2] conjunto 2: [18, (17, 13, 5, 15), 11, 20] , spt[1][2] Assim, com essa sobreposição de conjuntos, podemos pegar qualquer intervalo. */ int k = (int) floor(log((double) length) / log(2.0)); if (a[spt[i][k]] <= a[spt[j-(1<<k)+1][k]]) { return spt[i][k]; } else { return spt[j - (1<<k) + 1][k]; }}int main(){ int start, end, queries; cin >> n; for(int i=0; i< n; ++i) { cin >> a[i]; } build(); cin >> queries; while (queries--) { cin >> start >> end; cout << rmq(start,end) << endl; } return 0;}Entrada para teste:
7
18
17
13
5
15
11
20
1
0 4