17 · Sumas de prefijos
Grafos y consultas · Ruta de Aprendizaje
Antes de empezar. Arreglos, matrices y ciclos: 03 - Arreglos y búsqueda lineal y 04 - Matrices. No necesitas grafos.
Lectura para Regional
Estudia La idea, pasa a dos punteros y prueba el ejercicio «Un nuevo registro» más abajo. Las secciones de rectángulos y las aplicaciones que combinan mapas son ampliaciones.
🎯 Objetivos
Al terminar este módulo sabes:
- Responder “suma del rango [l, r]” en O(1) tras un precálculo O(n).
- Extender la idea a 2D (rectángulos) y a conteos acumulados.
- Reconocer la frase mágica: muchas consultas sobre datos que no cambian.
- Arrastrar una ventana con dos punteros cuando piden el rango más corto que cumple una condición.
📖 La lección
La idea
En {3,1,4,1,5}, queremos las sumas de [0,2], [1,3] y [0,4], con extremos incluidos. Sumarlas directamente da 8, 6 y 14, pero vuelve a leer varias veces las mismas casillas. Si hay muchas consultas, conviene guardar resultados compartidos: las sumas desde el inicio son 0,3,4,8,9,14. Una resta elimina el prefijo que sobra.
Primero veremos consultas sobre datos fijos; luego rectángulos y, como problema distinto, buscar una ventana.
pref[i] = suma de los primeros i elementos. Cualquier rango es una resta:
// supone: int n, l, r; vector<int> a; // a leído; [l, r] es la consulta
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
// suma de a[l..r] (0-indexado, inclusivo):
long long s = pref[r + 1] - pref[l]; // O(1) por consultaSi el diagrama no cabe, deslízalo horizontalmente.
La resta funciona porque pref[r + 1] incluye todo hasta r, y pref[l]
es exactamente la parte que sobra (todo hasta l - 1). El detalle que evita
el error de índices: pref tiene n + 1 casillas y pref[0] = 0, así el
rango que empieza en 0 también es una resta y no un caso aparte.
Sin esto, q consultas de rango cuestan O(n·q); con esto, O(n + q). Es la optimización con mejor razón beneficio/esfuerzo de toda la ruta — y el ejemplo perfecto de precalcular vs recalcular (Complejidad computacional).
Variantes que caen gratis
- Conteos acumulados: prefijos de “cuántos pares/vocales/unos hay hasta i”.
- 2D:
p[i][j]= suma de las primeras i filas y primeras j columnas; un rectángulo cualquiera sale con la inclusión-exclusión de 4 términos. - Diferencias: el truco inverso (sumar en un rango con dos marcas) — extensión opcional que se ilustra abajo.
La versión 2D, dibujada: restar los dos rectángulos sobrantes elimina dos veces su intersección, así que hay que sumarla una vez.
Si el diagrama no cabe, deslízalo horizontalmente.
Podemos comprobar la resta sin distraernos con los valores: si cada casilla vale 1, el total es 20. Quitamos las 5 de arriba y las 8 de la izquierda; las 2 de la esquina se quitaron dos veces, así que las recuperamos una vez. Quedan 9, exactamente las 3 × 3 casillas consultadas. Con otros valores se suman los contenidos de esas mismas regiones.
Si el diagrama no cabe, deslízalo horizontalmente.
Construir y consultar prefijos en dos dimensiones
Usaremos filas y columnas desde cero. p[i][j] suma las primeras i filas
y las primeras j columnas; la fila 0 y la columna 0 de p son ceros.
Para incluir a[i][j], unimos el rectángulo de arriba y el de la izquierda,
restamos su intersección (contada dos veces) y agregamos la casilla nueva.
// supone: int n, m; vector<vector<int>> a; // n filas y m columnas
vector<vector<long long>> p(n + 1, vector<long long>(m + 1, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
p[i + 1][j + 1] = p[i][j + 1] + p[i + 1][j] - p[i][j] + a[i][j];Para consultar filas f1..f2 y columnas c1..c2, ambos extremos incluidos:
// supone: int f1, f2, c1, c2; vector<vector<long long>> p;
long long suma_rectangulo = p[f2 + 1][c2 + 1] - p[f1][c2 + 1]
- p[f2 + 1][c1] + p[f1][c1];Los límites deben cumplir 0 <= f1 <= f2 < n y 0 <= c1 <= c2 < m.
En a = {{1, 2, 3}, {4, 5, 6}}, las filas de p son
{0, 0, 0, 0}, {0, 1, 3, 6} y {0, 5, 12, 21}.
La segunda fila, columnas 1 a 2, suma 5 + 6 = 11:
p[2][3] - p[1][3] - p[2][1] + p[1][1] = 21 - 6 - 5 + 1.
Construir cuesta O(n·m), consultar O(1), y las sumas deben caber en long long.
La página de referencia con las fórmulas completas: Sumas de prefijos.
La idea de diferencias, como extensión opcional, consiste en marcar
cuándo empieza y termina un aumento. Para sumar 3 a las posiciones 1..2
de cuatro ceros, marcas {0, 3, 0, -3}. Su suma acumulada da
{0, 3, 3, 0}: el aumento empieza en 1 y deja de aplicarse en 3.
La otra mitad: dos punteros y ventana deslizante
Los prefijos responden “¿cuánto suma este rango?”. Su complemento responde la pregunta inversa: “¿cuál es el rango más corto (o más largo) que cumple tal cosa?”. Ahí no quieres probar los O(n²) rangos posibles, sino arrastrar una ventana con dos índices que solo avanzan.
Buscamos un rango no vacío de suma al menos el objetivo, con todos los valores positivos. Agregar uno aumenta la suma; quitarlo la reduce. Esa condición es la que permite descartar comienzos sin tener que volver a ellos.
der extiende por la derecha. Después quitamos el elemento izquierdo
solo si la ventana restante todavía alcanza el objetivo. Así conservamos
la ventana válida más corta que termina en der. Por ejemplo, con {2,3,1,2}
y objetivo 7, la suma es 8: quitar el 2 dejaría 6, por lo que no lo quitamos.
Al añadir 4, la suma sube a 12: podemos quitar 2 y luego 3, y queda {1,2,4},
que suma 7. El código expresa exactamente esa comprobación.
Cada índice avanza como máximo n veces. El ciclo interior no vuelve al inicio para cada der: sus movimientos se reparten entre todas las vueltas. Por eso el costo total es O(n), aunque haya ciclos anidados.
// supone: int n; long long objetivo; vector<int> a; // con a[i] > 0
// el subarreglo MÁS CORTO cuya suma es >= objetivo
int izq = 0, largo = n + 1;
long long suma = 0;
for (int der = 0; der < n; der++) {
suma += a[der]; // estirar por la derecha
while (izq < der && suma - a[izq] >= objetivo) suma -= a[izq++]; // encoger
if (suma >= objetivo) largo = min(largo, der - izq + 1);
}Si al terminar largo == n + 1, no existe un rango no vacío que alcance el objetivo.
Con a = {2, 3, 1, 2, 4, 3} y objetivo = 7:
der | suma tras estirar | encoge (qué sale) | ventana [izq..der] | largo |
|---|---|---|---|---|
| 0 | 2 | — | [0..0] | ∞ (no llega a 7) |
| 1 | 5 | — | [0..1] | ∞ |
| 2 | 6 | — | [0..2] | ∞ |
| 3 | 8 | sacar el 2 dejaría 6: no | [0..3] | 4 |
| 4 | 12 | sale 2 → 10, sale 3 → 7 | [2..4] | 3 |
| 5 | 10 | sale 1 → 9, sale 2 → 7 | [4..5] | 2 |
Si el diagrama no cabe, deslízalo horizontalmente.
Respuesta: 2 (el {4, 3} del final).
El requisito escondido: esto funciona porque agregar elementos solo hace
crecer la suma y sacarlos solo la hace decrecer. Con números negativos la
ventana deja de ser monótona y hay que volver a prefijos (por eso Subarray
Sums II necesita un map y no dos punteros — está en la práctica).
Un contraejemplo concreto para este código es {5,−10,7}, objetivo 7. Sus sumas al extender son 5, −5 y 2; nunca intenta quitar el 5 porque hacerlo no alcanza el objetivo. Termina sin respuesta, aunque {7} sí sirve. El negativo impide deducir qué ocurre al mover los extremos. Los prefijos siguen siendo correctos con negativos, pero encontrar un rango óptimo exige otra estrategia.
La misma mecánica de “dos índices que solo avanzan” recorre dos listas ordenadas en paralelo; la ficha siguiente también desarrolla esa variante. Ficha completa: Dos punteros y ventana deslizante.
🏋️ Práctica
Práctica directa: Tres consultas sobre datos fijos
En {3,1,4,1,5}, con índices desde 0, responde sumas de [0,2], [1,3] y [0,4]. Salida: 8 6 14.
Idea para comprobar tu solución
Construye pref={0,3,4,8,9,14}. Por ejemplo [1,3] es pref[4]−pref[1]=9−3. Las consultas no modifican el arreglo.
Variación: Un nuevo registro
Para {4,-1,2,0,3}, responde las sumas de [0,0], [1,3] y [0,4], índices desde cero. Debes obtener 4 1 8. Después, para {1,4,2,1,5}, busca el largo mínimo de un rango no vacío con suma al menos 8: es 3.
Una pista, si la necesitas
Distingue consultar un rango dado de elegir sus extremos. ¿Cumple cada arreglo las condiciones de una ventana por suma?
Contrastar el razonamiento
Los prefijos del primero son
{0,4,3,5,5,8}y funcionan con el −1. En el segundo,{2,1,5}alcanza 8 y ningún elemento ni pareja adyacente llega. Allí todos los valores son positivos, así que la ventana monótona sí aplica.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Fórmula 1 | Nacional 2019 | prefijos en su forma más pura |
| 2 | Reloj inteligente | Regional 2018 | ventana deslizante sobre sumas |
| 3 | ⭐ Paltas Promedio | Regional 2019 | prefijos + map de primeras ocurrencias |
| 4 | ⭐⭐ Apuesta de alto riesgo | Regional 2024 | contar pares de prefijos (±1) |
| 5 | ⭐⭐ Cine | Nacional 2024 | junta los dos módulos: binaria sobre la respuesta + prefijos 2D |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Static Range Sum Queries (CSES 1646) | ★★ (—) | la definición, tal cual |
| 2 | Ilya and Queries (313B) | ★★ (1100) | prefijos de un conteo |
| 3 | Subarray Sums I (CSES 1660) | ★★★ (—) | prefijos + dos punteros |
| 4 | ⭐ Forest Queries (CSES 1652) | ★★★ (—) | prefijos 2D con inclusión-exclusión |
| 5 | ⭐ Subarray Sums II (CSES 1661) | ★★★★ (—) | prefijos + map (cuenta con negativos) |
Para pensar: prefijos que se repiten
Para a = {2, −2, 2}, los prefijos son {0, 2, 0, 2}.
¿Cuántos subarreglos no vacíos suman 2 y por qué hace falta contar
ocurrencias de cada prefijo, en vez de guardar solo si existe?
Si el diagrama no cabe, deslízalo horizontalmente.
Ver razonamiento
Hay tres: el primer
{2}, el último{2}y el arreglo completo. Un subarreglo suma 2 cuando su prefijo final menos su prefijo inicial vale 2. El primer prefijo 2 tiene un cero anterior; el segundo tiene dos. Por eso aporta1 + 2 = 3subarreglos. Un conjunto perdería la multiplicidad de esos ceros; un mapa de frecuencias la conserva. Consultar los prefijos anteriores antes de insertar el actual también evita contar un rango vacío cuando el objetivo es 0.
← 16 - Distancias en grafos · Ruta de Aprendizaje · 18 - Grafos II - Dijkstra y DAGs →