Resolva uma RMQ (consulta de intervalo mínimo) encontrando o LCA (menor ancestral comum)

Seja uma array A[0..N-1]. Para cada consulta [L, R] queremos encontrar o mínimo na array A começando na posição L e terminando na posição R. Assumiremos que a array A não muda no processo, ou seja, este artigo descreve uma solução para o problema estático de uma RMQ.

Aqui está uma descrição de uma solução assintoticamente ideal. Ele se destaca de outras soluções para o problema da RMQ, uma vez que é muito diferente delas: reduz o problema da RMQ ao problema do LCA e, em seguida, usa o algoritmo de Farach-Colton e Bender, que reduz o problema do LCA para um problema específico de uma RMQ.

Algoritmo

Construímos uma árvore Cartesiana da array A. Uma árvore Cartesiana de uma array A é uma árvore binária com a propriedade min-heap (o valor do nó parente deve ser menor ou igual ao valor de seus filhos) de modo que a travessia em ordem da árvore visita os nós na mesma ordem em que eles estão na array A.

Em outras palavras, uma árvore cartesiana é uma estrutura de dados recursiva. A array A será particionada em 3 partes: o prefixo da array até o mínimo, o mínimo e o sufixo restante. A raiz da árvore será um nó correspondente ao elemento mínimo da array A, a subárvore esquerda será a árvore cartesiana do prefixo e a subárvore direita será a árvore cartesiana do sufixo.

Na imagem a seguir, você pode ver uma array de tamanho 10 e a árvore cartesiana correspondente.

Image of Cartesian Tree

A consulta de intervalo mínimo [l, r] é equivalente à consulta do menor ancestral comum [l', r'], onde l' é o nó correspondente ao elemento A[l] e r' o nó correspondente ao elemento A[r]. De fato, o nó correspondente ao menor elemento do intervalo deve ser um ancestral de todos os nós do intervalo, portanto, também de l' e r'. Isso segue automaticamente a partir da propriedade min-heap. E também deve ser o menor ancestral, caso contrário, l' e r' estariam ambos na subárvore esquerda ou na direita, o que gera uma contradição, pois, nesse caso, o mínimo nem estaria no intervalo.

Na imagem a seguir, você pode ver as consultas de LCA para as consultas de RMQ [1, 3] e [5, 9]. Na primeira consulta, o LCA dos nós A[1] e A[3] é o nó correspondente a A[2] que tem o valor 2, e na segunda consulta, o LCA de A[5] e A[9] é o nó correspondente a A[8] que possui o valor 3.

LCA queries in the Cartesian Tree

Essa árvore pode ser construída em $O(N)$ e o algoritmo de Farach-Colton e Bender pode pré-processar a árvore em $O(N)$ e encontrar o LCA em $O(1)$.

Construção de uma árvore Cartesiana

Vamos construir a árvore cartesiana adicionando os elementos um após o outro. Em cada etapa, mantemos uma árvore cartesiana válida de todos os elementos processados. É fácil ver que a adição de um elemento s[i] só pode alterar os nós no caminho mais à direita - começando na raiz e repetidamente indo pelo filho direito - da árvore. A subárvore do nó com o menor, mas maior ou igual a s[i], valor se torna a subárvore esquerda de s[i], e a árvore com raiz s[i] se tornará a nova subárvore direita do nó com o maior, mas menor que s[i], valor.

Isso pode ser implementado usando um stack para armazenar os índices dos nós mais à direita.

vector<int> parent(n, -1);
stack<int> s;
for (int i = 0; i < n; i++) {
    int last = -1;
    while (!s.empty() && A[s.top()] >= A[i]) {
        last = s.top();
        s.pop();
    }
    if (!s.empty())
        parent[i] = s.top();
    if (last >= 0)
        parent[last] = i;
    s.push(i);
}