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))$$
https://gist.github.com/Thiago4532/cda4a231e742169be857bc18cf0f5cc7
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:
https://gist.github.com/Thiago4532/7e484738361d5fe8726e82d164740003
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.