Treino T05: Intervalos com Orçamento

Os Artigos 13 a 16 trataram o capítulo dos arrays como uma recusa sistemática de refazer trabalho. As somas de prefixo pagam uma passada para que cada soma de intervalo custe duas leituras. Os arrays de diferenças prometem as atualizações em vez de executá-las. As janelas deslizantes mantêm só o estado que muda quando um elemento entra e outro sai. A sparse table (tabela de respostas pré-calculadas para blocos de potência de 2) troca a inversa, que o mínimo não tem, pela idempotência. Os bits fazem $64$ operações de conjunto por instrução. O hash de prefixo transforma um trecho em um número, e o algoritmo de Mo reordena as perguntas para que uma janela ande pouco. Este treino cobra essas recusas com o relógio correndo.

A pergunta que atravessa os sete problemas é sempre a mesma, com roupas diferentes. O que o passo anterior já sabe, e quanto custa não esquecer? Encontrar a resposta depende de reconhecer o tipo de pergunta: atualizações antes de qualquer leitura, uma janela de tamanho fixo, uma janela que cresce e encolhe, consultas sobre um vetor imutável ou perguntas que podem ser respondidas em qualquer ordem.