Escrito por Thiago Mota
Pense no seguinte problema, dado um vetor de $$N$$ elementos iremos fazer $$Q$$ perguntas no vetor do tipo $$[l, r]$$ perguntando qual o menor valor do vetor no intervalo de $$l$$ até $$r$$. Esse problema pode ser facilmente resolvido utilizando uma Segment Tree com a complexidade de $$O(q \log n)$$ para cada pergunta, mas nesse problema não temos update logo não é necessário o uso da Segment Tree, logo iremos resolver utilizando uma técnica de “programação dinâmica”.
Iremos definir uma tabela $$tab$$ de tal forma que $$tab(i, j)$$ seja o menor valor no intervalo que começa em $$i$$ e tem tamanho $$2^j$$, ou seja, para o vetor $$v = [1, 5, 3, 6, 2]$$ teremos a seguinte tabela:
$$tab(1, 0) = 1 \: [1, 1]$$
$$tab(1, 1) = 1 \: [1, 2]$$
$$tab(1, 2) = 1 \: [1, 4]$$
$$tab(2, 0) = 5 \: [2, 2]$$
$$tab(2, 1) = 3 \: [2, 3]$$
$$tab(2, 2) = 2 \: [2, 5]$$
$$tab(3, 0) = 3 \: [3, 3]$$
$$tab(3, 1) = 3 \: [3, 4]$$
$$tab(4, 0) = 6 \: [4, 4]$$
$$tab(4, 1) = 2 \: [4, 5]$$
$$tab(5, 0) = 2 \: [5, 5]$$
O tamanho dessa tabela será por volta de $$O(n \log n)$$ de memória, pois o segundo argumento só vai até o logaritmo do tamanho total.
Para computar essa tabela, iremos olhar paras os valores calculados anteriormente, olhe para a imagem:
Com isso, notamos que para calcular a $$tab(i, j)$$ podemos olhar o menor entre $$tab(i, j-1)$$ e $$tab(k, j-1)$$, sendo $$k$$ o início do próximo intervalo, como o tamanho do intervalo é $$2^{j-1}$$, o $$k$$ vai ser $$i + 2^{j-1}$$, logo:
$$tab(i, j) = min(tab(i, j-1), tab(i + 2^{j-1}, j-1))$$
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // (n) é o tamanho do vetor | |
| // (log_n) é o log na base 2 de n | |
| // (v) é o vetor | |
| void computa() { | |
| // Caso inicial (tamanho 1, j = 0) | |
| for (int i = 1; i <= n; i++) | |
| tab[i][0] = v[i]; // Intervalo [i, i] | |
| for (int j = 1; j <= log_n; j++) { | |
| // Note que o for do j vem primeiro, isso é necessário pois | |
| // o jeito que tab(i, j) é calculado necessita que todos os i's | |
| // para j-1 estejam calculados. | |
| for (int i = 1; i <= n; i++) { | |
| // Checando se o intervalo que começa em i e tem tamanho 2^j existe. | |
| // Para isso basta checar se o fim do intervalo é menor ou igual a n | |
| if (i + (1<<j) – 1 > n) break; | |
| tab[i][j] = min(tab[i][j-1], tab[i + (1<<(j-1))][j-1]); | |
| } | |
| } | |
| } |
Agora para calcular o mínimo de qualquer intervalo $$[l, r]$$ iremos simplesmente calcular o $$k = \left \lfloor{\log_2 tam}\right \rfloor$$ sendo $$tam$$ o tamanho do intervalo e pegar o mínimo dos intervalos que começam em $$l$$ e tem tamanho $$2^k$$, ou seja, $$tab(l, k)$$ e outro que termina e $$r$$ e tem tamanho $$2^k$$, ou seja, $$tab(r – 2^k + 1, k)$$, tendo assim o mínimo do intervalo todo.
Segue o código:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // (n) é o tamanho do vetor | |
| // (v) é o vetor | |
| int flog(int x) { // Calcula a parte inteira do log2 de x em O(1) ( para int ) | |
| return 31 – __builtin_clz(x); | |
| } | |
| int flog(long long x) { // Calcula a parte inteira do log2 de x em O(1) ( para long long ) | |
| return 63 – __builtin_clzll(x); | |
| } | |
| int query(int l, int r) { | |
| int k = flog(r – l + 1); | |
| return min(tab[l][k], tab[r – (1<<k) + 1][k]); | |
| } |
Note que essa tabela só funciona pois o menor entre $$x$$ e $$x$$ é o próprio $$x$$, pois existe sobreposição de intervalos na hora de fazer a query, ou seja, não funcionaria caso a pergunta fosse a soma do intervalo.
Essa ideia de montar uma tabela nas potências de dois tem o nome de Sparse Table e é muito utilizada na hora de calcular valores em uma árvore como no Menor Ancestral Comum, uma questão que usa uma ideia similar é a Crayfish Scrivener dá IOI 2012 caso você queira exercitar a ideia.