Somas de Prefixos e Totais Acumulados
Crie arrays de somas de prefixos para responder a consultas de soma em intervalos em O(1) e aplique a técnica a problemas de subarrays, como o subarray de soma máxima.
Somas de Prefixos e Totais Acumulados é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 2 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O Problema da Soma de Intervalos
Dado um vetor nums, é necessário responder a muitas consultas no formato: qual é a soma dos elementos do índice i ao índice j? Calcular cada consulta de forma ingênua leva O(n), portanto k consultas custam O(n×k). Com um vetor de somas prefixadas, você pré-computa um total acumulado em O(n) e depois responde a cada consulta em O(1). Esta é uma das técnicas de pré-computação mais usadas em entrevistas.
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operationsConstruindo o Vetor de Soma Prefixada
Defina prefix[i] como a soma de nums[0] até nums[i-1] (uma posição extra; o deslocamento de índice a partir de zero em 1 torna os casos de limite mais simples). Construa-o em O(n) with uma única passagem: prefix[i] = prefix[i-1] + nums[i-1]. Então, uma consulta de intervalo sum(i, j) se torna prefix[j+1] - prefix[i]: uma única subtração com custo O(1).
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15Soma de Subvetor Igual a K
Encontrar a quantidade de subvetores cuja soma é igual a k é um problema clássico de mapa de dispersão + soma prefixada. A ideia fundamental é: a soma do subvetor do índice i ao j é igual a prefix[j] - prefix[i-1]. Se quisermos que isso seja igual a k, então prefix[i-1] = prefix[j] - k. Ao percorrer da esquerda para a direita, mantendo uma soma prefixada acumulada, verificamos quantas vezes current_sum - k apareceu antes, contando todos os subvetores válidos em O(n) no total.
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])Soma Máxima de Subvetor com Prefixos
A soma máxima de um subvetor pode ser formulada como um problema de soma prefixada: para cada índice j, queremos maximizar prefix[j] - prefix[i] para todos os valores de i < j. O i ideal em cada j é a menor soma prefixada vista até então. Percorrer da esquerda para a direita acompanhando min_prefix resulta em tempo O(n). Isso equivale ao algoritmo de Kadane visto pela perspectiva das somas prefixadas.
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1Somas Prefixadas 2D para Consultas em Grade
As somas prefixadas também se estendem a grades bidimensionais. Defina P[i][j] como a soma de todos os elementos do retângulo de (0,0) a (i-1,j-1). Construa-o com a fórmula de inclusão-exclusão: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Assim, qualquer consulta da soma do retângulo de (r1,c1) a (r2,c2) pode ser respondida em O(1) usando quatro consultas.
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14Total Acumulado para o Índice de Equilíbrio
O índice de equilíbrio é a posição em que a soma dos elementos à esquerda é igual à soma dos elementos à direita. Pré-compute a soma total e depois percorra o vetor mantendo uma soma acumulada à esquerda. A soma à direita é total - left_sum - nums[i]. Verifique a igualdade em O(1) para cada índice, totalizando O(n). Isso demonstra como um total acumulado substitui dois vetores separados de somas prefixadas.
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1Produto do Vetor Exceto o Próprio Elemento
Dado um vetor, retorne um vetor em que cada elemento é o produto de todos os outros. A divisão não é permitida. Use um produto de prefixo e um produto de sufixo: resultado[i] = (produto de todos os elementos anteriores a i) × (produto de todos os elementos posteriores a i). Construa os produtos dos prefixos em uma passagem da esquerda para a direita e depois multiplique pelos produtos dos sufixos em uma passagem da direita para a esquerda usando uma variável acumulada — não é necessário um vetor adicional para o sufixo.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra spaceSoma Prefixada com Módulo
Alguns problemas pedem a quantidade de subvetores cuja soma é divisível por k. Usando somas prefixadas módulo k: se prefix[j] % k == prefix[i] % k, então sum(i+1..j) é divisível por k. Um mapa de dispersão que conta cada valor de resto à medida que percorremos o vetor oferece tempo O(n). A inicialização fundamental é freq[0] = 1 para tratar subvetores que começam no índice 0.
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)Vetor de Diferenças para Atualizações de Intervalo
Um vetor de diferenças é o inverso de uma soma prefixada. Dado um vetor, pré-compute diff[i] = nums[i] - nums[i-1]. Adicionar x a um intervalo [l, r] exige apenas duas operações O(1) no vetor de diferenças: diff[l] += x e diff[r+1] -= x. Depois de todas as atualizações, reconstrua o vetor de resultado com uma única passagem de soma prefixada. Isso transforma k atualizações de intervalo de O(n×k) em O(n + k).
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]Soma Prefixada em Problemas de Entrevista
As somas prefixadas aparecem em muitas categorias de problemas:
- Consultas de intervalo — soma de subvetor, soma de retângulo
- Contagem de subvetores — soma igual a k, divisível por k
- Problemas de produto — produto exceto o próprio elemento
- Equilíbrio — encontrar o índice de pivô
- Atualizações de intervalo — vetor de diferenças
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3Soma Acumulada e Máximo Acumulado
Além das somas prefixadas, muitos problemas usam um máximo acumulado ou mínimo acumulado mantido with uma única variável. O problema do melhor momento para comprar ações usa um preço mínimo acumulado; capturar água da chuva a partir da esquerda usa uma altura máxima acumulada à esquerda. Esses padrões exigem apenas uma passagem e espaço adicional O(1), tornando-se o padrão-ouro tanto para eficiência de tempo quanto de espaço.
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: as somas prefixadas transformam consultas de intervalo O(n) em consultas O(1) ao pré-computar somas acumuladas em uma única passagem O(n), combinar somas prefixadas com um mapa de dispersão permite soluções O(n) para contar subvetores com uma determinada soma ou propriedade de divisibilidade e os vetores de diferenças são o inverso: permitem atualizações de intervalo O(1) com uma única passagem de reconstrução por soma prefixada ao final. A seguir, abordaremos a técnica de dois ponteiros, começando com ponteiros nas extremidades opostas.
Perguntas Frequentes
A aula “Somas de Prefixos e Totais Acumulados” é grátis?
Sim — o texto completo de “Somas de Prefixos e Totais Acumulados” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Somas de Prefixos e Totais Acumulados”?
Crie arrays de somas de prefixos para responder a consultas de soma em intervalos em O(1) e aplique a técnica a problemas de subarrays, como o subarray de soma máxima. Você pratica DSA Interview Prep 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep 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 2 de 4.
Quanto tempo leva a aula “Somas de Prefixos e Totais Acumulados”?
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 DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep 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
- Fundamentos de Arrays e Operações In-Place
- Somas de Prefixos e Totais Acumulados
- Dois Ponteiros: Extremidades Opostas
- Dois Ponteiros: Lento e Rápido