Crie um Array de Somas de Prefixos
Pré-calcule os totais acumulados uma vez.
Crie um Array de Somas de Prefixos é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O Problema das Somas Repetidas
Imagine responder a centenas de perguntas sobre somas de intervalos em um único vetor. Somar cada intervalo desde o início é lento. Uma soma prefixada resolve esse problema. 🚀
O Que é uma Soma Prefixada
Um vetor de somas prefixadas armazena, em cada índice, o total de todos os elementos até aquele ponto. Uma única passagem de pré-cálculo transforma somas lentas em respostas instantâneas.
Um Pequeno Exemplo
Para [3, 1, 4], os totais acumulados são 3, depois 4 e, por fim, 8. Essa lista crescente de totais é exatamente a sua soma prefixada.
A Recorrência Principal
Cada entrada é o total anterior mais o elemento atual. Essa recorrência de uma linha é o coração de toda a técnica.
prefix[i] = prefix[i - 1] + a[i]Construa-a no Código
Percorra o vetor uma vez, mantendo um total acumulado. A cada etapa, use append para adicionar a nova soma, portanto construir o vetor é uma única passagem linear.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Por Que um Zero Inicial Ajuda
Começar prefix com um zero inicial significa que prefix[i] armazena a soma dos primeiros i elementos. Isso simplifica os cálculos de intervalos mais adiante.
Convenção de Índices
Com o zero no início, prefix[k] é igual a a[0] + ... + a[k-1]. Manter essa convenção correta evita erros dolorosos de deslocamento de um índice.
Custo da Construção
Construir o vetor de somas prefixadas acessa cada elemento exatamente uma vez, portanto custa O(n) de tempo. Você paga esse custo uma vez e depois reutiliza o resultado indefinidamente.
Pré-calcule uma Vez, Consulte Muitas
A grande vantagem é o compromisso: faça uma passagem linear inicial para que cada consulta posterior de soma se torne uma busca rápida, em vez de um laço.
Um Atalho em Python
A biblioteca padrão pode construir os totais para você. itertools.accumulate produz as somas acumuladas em uma única chamada organizada.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Fique Atento à Memória
O vetor de somas prefixadas tem o mesmo tamanho da entrada, mais um. Para entradas enormes, lembre-se de que ele dobra o uso de memória.
Verificação Rápida
Você constrói um vetor de somas prefixadas. O que o índice 0 costuma armazenar?
Recapitulação
Você aprendeu a construir um vetor de somas prefixadas em uma passagem O(n), usando um zero inicial para simplificar os índices. Faça o pré-cálculo uma vez e reutilize-o. ✅
Perguntas Frequentes
A aula “Crie um Array de Somas de Prefixos” é grátis?
Sim — o texto completo de “Crie um Array de Somas de Prefixos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Crie um Array de Somas de Prefixos”?
Pré-calcule os totais acumulados uma vez. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Crie um Array de Somas de Prefixos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Crie um Array de Somas de Prefixos
- Some Qualquer Intervalo com Subtração
- Conte Subarrays com uma Soma-Alvo
- Arrays de Diferenças para Atualizações de Intervalos