Some Qualquer Intervalo com Subtração

Construir o vetor de somas prefixadas foi apenas a preparação. Agora vem a parte mágica: responder a qualquer soma de intervalo com uma única subtração. ⚡

Uma soma de intervalo é apenas um total grande menos um menor. Subtrair dois valores de soma prefixada cancela de forma organizada tudo que está fora do seu intervalo.

Para somar os elementos de l a r, subtraia prefix[l] de prefix[r + 1]. Essa única fórmula funciona para qualquer intervalo.

prefix[r + 1] contém tudo até r, e prefix[l] contém tudo antes de l. A diferença deixa exatamente o trecho do meio.

Para [3, 1, 4], o prefixo é [0, 3, 4, 8]. Para somar os índices de 1 a 2, faça 8 menos 3, o que dá 5. Isso corresponde a 1 mais 4.

Cada consulta é apenas uma subtração, então é executada em O(1). Mil consultas têm o mesmo custo por consulta que uma única.

O deslize mais comum está no índice do limite superior. Com um zero inicial, você sempre usa prefix[r + 1], não prefix[r]. Verifique esse limite.

Decida logo no início se r está incluído. Esta fórmula trata o intervalo como inclusivo em l e r, que é o que a maioria dos problemas de competições espera.

Uma pequena função auxiliar mantém sua lógica legível e seus índices em um só lugar. Use esta função auxiliar em vez de inserir a matemática diretamente.

Para somar o vetor inteiro, use l igual a 0 e r igual a n menos 1. A fórmula fornece prefix[n], o total geral.

Sempre que um problema fizer muitas perguntas de soma de intervalos em um vetor fixo, as somas de prefixos transformam um laço O(n) por consulta em respostas instantâneas.

Você quer a soma dos índices de l a r, inclusive.

Agora você pode responder a qualquer soma de intervalo em O(1) com prefix[r + 1] menos prefix[l]. Tenha cuidado com o deslocamento causado pelo zero inicial para evitar erros. ✅