Consultas de Intervalo Mínimo (Range Minimum Query)

RMQ

Você recebe uma array $A[1..N]$. Você deve responder às consultas da forma $(L, R)$, que solicitam encontrar o elemento mínimo na array $A$ entre as posições $L$ e $R$.

RMQ podem aparecer em problemas diretamente ou podem ser aplicadas em outras tarefas, por exemplo, o problema do Menor Ancestral Comum.

Solução

Existem várias abordagens e estruturas de dados possíveis que você pode usar para resolver a tarefa da RMQ.

As que são explicadas neste site estão listadas abaixo.

Primeiro, as abordagens que permitem modificações na array enquanto respondemos consultas.

E aqui estão as abordagens que funcionam apenas em arrays estáticas, ou seja, não é possível alterar um valor na array sem recalcular a estrutura de dados completamente.

Nota: O pré-processamento é o processamento preliminar da array fornecida, criando uma estrutura de dados correspondente para ela.

Problemas