Somas de Prefixo e Arrays de Diferenças: Integrar e Derivar em Tempo Constante

O Artigo 12 fechou o bloco de busca e ordenação, e este artigo abre o capítulo dos arrays unidimensionais (vetores de uma dimensão). Um array é a estrutura mais simples da série e, justamente por isso, uma das mais perigosas. Ele parece inofensivo. Então um enunciado pede ${10}^5$ consultas de intervalo sobre ${10}^5$ elementos, a leitora escreve dois laços aninhados, e o juiz responde com a delicadeza de uma porta trancada.

O Artigo 5 apresentou as somas de prefixo como ferramenta, com a armadilha do acumulador do std::partial_sum e a tabela em duas dimensões. Este artigo volta a elas para entendê-las por dentro. A soma de prefixo é uma integral discreta, a diferença entre vizinhos é uma derivada discreta, e as duas desfazem uma à outra. Dessa relação saem quase todas as técnicas do artigo: consultas de soma em tempo constante, contagens por categoria, atualizações de intervalo com duas escritas, a versão em duas dimensões das atualizações e a atualização incremental de um agregado. No fim, as medições no MSVC mostram que a mesma construção dos prefixos pode custar o dobro conforme a forma do laço, e o código de máquina explica o motivo.

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-13.