Janelas que Deslizam: Deque Monotônico, Dois Ponteiros, Kadane e Sparse Table

O Artigo 13 respondeu às duas primeiras perguntas do capítulo dos arrays: como pré-processar um vetor fixo para consultas rápidas e como representar atualizações de intervalo sem tocar cada elemento. Este artigo trata da terceira: como mover uma janela pelo vetor mantendo apenas o estado necessário?

Uma janela é um trecho contíguo $[l,r]$ do vetor. Quando ela anda uma posição para a direita, um elemento sai pela esquerda e outro entra pela direita, e todo o resto continua lá. Recalcular a janela inteira a cada passo ignora essa sobreposição e paga $k$ operações onde bastariam duas. As técnicas deste artigo mantêm um estado pequeno que se atualiza com o que entra e o que sai: uma soma, um deque de candidatos, um par de ponteiros ou a melhor soma de um trecho que termina na posição atual. A sparse table (tabela de respostas pré-calculadas para blocos de potência de 2), no fim, responde ao problema que as somas de prefixo não resolvem, o mínimo de um intervalo arbitrário, e explica por que a subtração que funcionava para somas não funciona para mínimos.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, salvo onde o texto disser outra coisa. Os programas deste artigo, com as entradas e as saídas esperadas de cada caso de teste, estão em serie-blog/competitiva-14.

1. A janela de tamanho fixo

O caso mais simples tem uma janela de $k$ posições e uma soma a manter. A soma da janela que começa na posição $i$ será dada por

$$S_i=a_i+a_{i+1}+\cdots +a_{i+k-1},$$