O que é prefix sum?
Imagina que você tem um array gigante com milhares de números
(ex: dados de vendas diárias de um ano).
Agora, você precisa responder perguntas como:
- "Qual foi o total de vendas entre o dia 15 e o dia 45?"
ou - "E entre o dia 100 e o 200?"
Mas e se seu software atende milhares de empresas e você precisar responder perguntas como estas, milhares de vezes?
A forma mais direta seria usar um loop para cada pergunta, somando os valores um por um.
Mas se tiver milhares dessas consultas, o programa vai ficar muito lento!
O que é a Soma Acumulada (Prefix Sum)?
A ideia é simples: antes de precisar responder
"Qual foi o total de vendas entre o dia 15 e o dia 45?",
você cria um novo array (vamos chamá-lo de presum) que "pré-calcula" as somas.
Cada posição ( i ) desse novo array presum vai guardar a soma de todos os elementos antecedentes do array original, do início (índice 0) até a posição i.
Ou seja, cada posição do presum guarda quanto você já somou até aquele ponto em relação ao array original.
Exemplo:
Array Original: [10, 5, 8, 2, 7]
Array presum (Soma Acumulada):
presum[0] = 10
presum[1] = 10 + 5 = 15
presum[2] = 15 + 8 = 23
presum[3] = 23 + 2 = 25
presum[4] = 25 + 7 = 32
presum final: [10, 15, 23, 25, 32]
A Mágica da Subtração
Agora vem a parte legal.
Como usamos isso para achar a soma de uma "fatia" (um range)?
Digamos que queremos a soma do índice 1 ao 2 de [5, 8, 2].
array.values = [5, 8, 2]
array.presum = [5, 13, 15]
Nosso startRange é 1 e nosso finalRange é 2.
1. Pegue a soma total ATÉ o final do seu intervalo do presum.
O nosso finalRange é 2.
Se olharmos no array.presum[2] , o valor é 15.
Esse número 15 representa a soma de TUDO desde o início (índice 0) até o índice 2 (finalRange).
array.presum[2] = (5 + 8 + 2) = 15
vou chamar esse valor de 15 de "ateOndeEuQuero"
ateOndeEuQuero = array.presum[2]
2. Descubra a parte que você NÃO quer.
ateOndeEuQuero é quase o que queremos,
mas ele inclui coisas antes do nosso startRange.
Nós só queremos começar do índice 1 (startRange).
A parte que não queremos é tudo o que vem antes do índice 1.
Neste caso, é apenas o índice 0 (o valor 5).
3. Onde achar a soma da parte que você NÃO quer?
A soma de tudo que vem antes do nosso startRange (índice 1) já está calculada!
Ela está guardada no presum na posição array.presum[ 0 ] .
Ou seja,
array.presum[ startRange - 1 ],
que é array.presum[0]. O valor é 5.
vou chamar de oQueEuNaoQuero
oQueEuNaoQuero = array.presum[ startRange - 1]
4. Pegue o total e só tire o que você não quer!
Agora é só subtrair o que você não quer (5) do total que você pegou (15).
apenasOqueEuQuero = ateOndeEuQuero - oQueEuNaoQuero
apenasOqueEuQuero = 15 - 5 = 10
Vamos checar:
a soma de [-, 8, 2] é 8 + 2 = 10. Funcionou!
arr.values = [5, 8, 2]
array.presum = [5, 13, 15]
startRange = 1
finalRange = 2
ateOndeEuQuero = array.presum[ finalRange ]
oQueEuNaoQuero = array.presum[ startRange - 1 ]
apenasValorQueEuQuero = ateOndeEuQuero - oQueEuNaoQuero
Operamos com as posições desejadas no array de prefixos, esse é o grande poder, já lidamos com as somas précalculadas para obter a fatia de soma que queremos.
É obvio que nesse caso não fez muito sentido fazer tudo isso, era só a soma de dois valores.
Conclusão
Nem sempre vamos precisar de soma de intervalos, mas quando precisarmos, já vão estar prontas.
Podemos atualizar o array preSum sempre que os valores mudam, ou forem incrementados (se for o caso de uma lista).
Criação do array preSum
Criar o array preSum exige somar todos os elementos uma vez, um após o outro:
Você percorre o array original uma única vez, então o tempo total é proporcional ao tamanho do array — ou seja, O(n).
Consultas no preSum
Você só faz duas consultas diretas e uma subtração:
- Cada uma dessas operações é instantânea (acesso direto a índice de array + subtração).
- Elas não dependem do tamanho do array, nem do tamanho do intervalo.
Por isso, o tempo de execução é constante — O(1).
Ao gastar um tempinho no início para criar o array preSum um processo O(n)
você ganha o poder de responder qualquer soma de "fatias" em um tempo O(1).
⚠️ Mas atenção:
É importante perceber que calcular um presum ira consumir o dobro de mémoria do array original, e só fara sentido se tiver muitas requisições como essas.
Use presum em casos que os dados não mudam (são estáticos).
Mudam Raramente (Ex: Análise de dados históricos):
✅O Prefix Sum é a ferramenta ideal.
Mudam Sempre (Ex: Sistema de vendas ao vivo):
❌O Prefix Sum básico é ineficiente.
