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))$$
| // (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.
| // (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.

