Sumas de prefijos y totales acumulados
Construya arrays de sumas de prefijos para responder consultas de sumas de rangos en O(1) y aplique la técnica a problemas de subarrays, como el subarray de suma máxima.
Sumas de prefijos y totales acumulados es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
El problema de la suma de rangos
Dado un array nums, debe responder muchas consultas de la forma: ¿cuál es la suma de los elementos desde el índice i hasta el índice j? Calcular cada consulta de forma ingenua cuesta O(n), por lo que k consultas cuestan O(n×k). Con un array de sumas de prefijos, precalcula un total acumulado en O(n) y luego responde cada consulta en O(1). Esta es una de las técnicas de precomputación más utilizadas en las 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 operationsConstruir el array de sumas de prefijos
Defina prefix[i] como la suma de nums[0] hasta nums[i-1] (hay una posición adicional; el desplazamiento de 1 con indexación desde cero simplifica los casos límite). Constrúyalo en O(n) mediante una sola pasada: prefix[i] = prefix[i-1] + nums[i-1]. Después, una consulta de rango sum(i, j) se convierte en prefix[j+1] - prefix[i]: una sola resta con un coste de 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)) # 15Suma de un subarray igual a K
Encontrar el número de subarrays cuya suma es igual a k es un problema clásico de mapa hash y suma de prefijos. La idea clave es que la suma del subarray de i a j equivale a prefix[j] - prefix[i-1]. Si queremos que sea igual a k, entonces prefix[i-1] = prefix[j] - k. Al recorrer de izquierda a derecha y mantener una suma de prefijos acumulada, consultamos cuántas veces ha aparecido antes current_sum - k y contamos todos los subarrays válidos en O(n) en 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])Suma máxima de un subarray mediante prefijos
La suma máxima de un subarray puede formularse como un problema de sumas de prefijos: para cada índice j, queremos maximizar prefix[j] - prefix[i] para todos los i < j. El i óptimo en cada j es la suma de prefijos mínima observada hasta ese momento. Recorrer de izquierda a derecha mientras se realiza un seguimiento de min_prefix proporciona un tiempo O(n). Esto equivale al algoritmo de Kadane visto desde la perspectiva de las sumas de prefijos.
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]))
# -1Sumas de prefijos 2D para consultas sobre cuadrículas
Las sumas de prefijos también se extienden a las cuadrículas 2D. Defina P[i][j] como la suma de todos los elementos del rectángulo desde (0,0) hasta (i-1,j-1). Constrúyalo mediante la fórmula de inclusión-exclusión: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Después, cualquier consulta de suma de un rectángulo desde (r1,c1) hasta (r2,c2) se responde en O(1) mediante cuatro 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 el índice de equilibrio
El índice de equilibrio es la posición en la que la suma de los elementos de la izquierda coincide con la suma de los de la derecha. Precalcule la suma total y, después, recorra el array manteniendo una suma izquierda acumulada. La suma derecha es total - left_sum - nums[i]. Compruebe la igualdad en O(1) por índice, lo que da un total de O(n). Esto demuestra cómo un total acumulado sustituye a dos arrays separados de sumas de prefijos.
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])) # -1Array de productos excepto el propio elemento
Dado un array, devuelva otro en el que cada elemento sea el producto de todos los demás. No se permite usar división. Utilice un producto prefijo y un producto sufijo: result[i] = (producto de todos los elementos anteriores a i) × (producto de todos los elementos posteriores a i). Construya los productos prefijo en una pasada de izquierda a derecha y, después, multiplíquelos por los productos sufijo en una pasada de derecha a izquierda usando una variable acumulada; no se necesita un array adicional para el sufijo.
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 spaceSuma de prefijos con módulo
Algunos problemas solicitan el número de subarrays cuya suma es divisible por k. Si usamos sumas de prefijos módulo k: cuando prefix[j] % k == prefix[i] % k, entonces sum(i+1..j) es divisible por k. Un mapa hash que cuente cada valor del resto a medida que recorremos el array proporciona un tiempo O(n). La inicialización clave es freq[0] = 1, para gestionar los subarrays que comienzan en el í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)Array de diferencias para actualizaciones de rangos
Un array de diferencias es el inverso de una suma de prefijos. Dado un array, precalcule diff[i] = nums[i] - nums[i-1]. Añadir x a un rango [l, r] solo requiere dos operaciones O(1) sobre el array de diferencias: diff[l] += x y diff[r+1] -= x. Después de todas las actualizaciones, reconstruya el array de resultados mediante una sola pasada de sumas de prefijos. Esto transforma k actualizaciones de rangos de O(n×k) a 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]Sumas de prefijos en problemas de entrevistas
Las sumas de prefijos aparecen en muchas categorías de problemas:
- Consultas de rangos — suma de subarray, suma de rectángulo
- Conteo de subarrays — suma igual a k, divisible por k
- Problemas de productos — producto excepto el propio elemento
- Equilibrio — encontrar el índice de pivote
- Actualizaciones de rangos — array de diferencias
# 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)) # 3Suma acumulada y máximo acumulado
Más allá de las sumas de prefijos, muchos problemas utilizan un máximo acumulado o un mínimo acumulado que se mantiene en una sola variable. El problema de comprar y vender acciones en el mejor momento utiliza un precio mínimo acumulado; atrapar agua de lluvia desde la izquierda utiliza una altura máxima acumulada a la izquierda. Estos patrones solo requieren un recorrido y espacio adicional O(1), lo que los convierte en la referencia de eficiencia tanto temporal como espacial.
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])) # 5Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: las sumas de prefijos transforman las consultas de rangos O(n) en consultas O(1) al precalcular las sumas acumuladas en una sola pasada O(n), combinar sumas de prefijos con un mapa hash permite soluciones O(n) para contar subarrays con una suma determinada o una propiedad de divisibilidad, y los arrays de diferencias son el inverso: permiten realizar actualizaciones de rangos O(1) y reconstruir el resultado mediante una sola pasada final de sumas de prefijos. A continuación abordaremos la técnica de dos punteros, comenzando con punteros en extremos opuestos.
Aprende Python con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 30
- Lecciones
- 120
Preguntas frecuentes
¿La lección «Sumas de prefijos y totales acumulados» es gratis?
Sí — el texto completo de «Sumas de prefijos y totales acumulados» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Sumas de prefijos y totales acumulados»?
Construya arrays de sumas de prefijos para responder consultas de sumas de rangos en O(1) y aplique la técnica a problemas de subarrays, como el subarray de suma máxima. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Sumas de prefijos y totales acumulados»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Fundamentos de arrays y operaciones in-place
- Sumas de prefijos y totales acumulados
- Dos punteros: extremos opuestos
- Dos punteros: lento y rápido