🧱 Sumas de prefijos
Estructura de datos · Se implementa a mano · Tema: Estructuras de Datos Catálogo completo: Catálogo de estructuras
📍 Dónde se aprende: módulo 17 de la Ruta de Aprendizaje.
El problema: muchas preguntas sobre el mismo arreglo
Usaremos a = [3, 1, 4, 2, 5, 0, 2, 1], con índices desde 0.
Queremos responder preguntas como «¿cuánto suman las posiciones 2 a 6?».
Sumarlas directamente da 4 + 2 + 5 + 0 + 2 = 13, pero repite trabajo cuando
las consultas se superponen. Con q consultas, el costo puede llegar a O(nq).
Podemos guardar la suma desde el comienzo hasta cada frontera del arreglo. Así una consulta necesita solo dos valores que ya calculamos.
La resta que deja exactamente el intervalo
Definimos pre[i] como la suma de los primeros i elementos. Por eso
pre[0] = 0: no hay elementos antes de empezar. El arreglo de prefijos tiene
n + 1 posiciones, una más que el original.
Si el diagrama no cabe, deslízalo horizontalmente.
| i: cantidad de elementos incluidos | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| pre[i] | 0 | 3 | 4 | 8 | 10 | 15 | 15 | 17 | 18 |
Para consultar [2, 6], pre[7] incluye las posiciones 0…6.
Restamos pre[2], que contiene 0…1. Lo compartido se cancela y queda
exactamente 2…6: 17 − 4 = 13.
En general, para un intervalo cerrado [l, r]:
suma(l, r) = pre[r + 1] − pre[l].
No hay un caso especial cuando l = 0: se resta pre[0], que vale cero.
Para un único elemento, suma(2, 2) = pre[3] − pre[2] = 8 − 4 = 4.
Por qué funciona y cuánto cuesta
Construimos cada prefijo con pre[i + 1] = pre[i] + a[i]. Si pre[i]
representa correctamente los primeros i elementos, añadir el siguiente
produce el prefijo correcto de tamaño i + 1. El caso inicial es la suma vacía.
| Operación | Tiempo | Razón |
|---|---|---|
| Construir | O(n) | una suma por elemento |
| Consultar un intervalo | O(1) | dos accesos y una resta |
| Cambiar un elemento y mantener los prefijos | O(n) en el peor caso | modifica todos los prefijos que lo incluyen |
| Memoria adicional | O(n) | n + 1 sumas acumuladas |
Los valores negativos también funcionan: la cancelación no depende de que las sumas crezcan. Sí debemos usar un tipo donde quepan las sumas acumuladas, no solo los valores individuales.
Implementación: una dimensión y su extensión a una grilla
// 1D: pre[i] = suma de los primeros i elementos (pre[0] = 0, n + 1 casillas)
vector<long long> prefijos(const vector<long long>& a) {
int n = a.size();
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
return pre;
}
// suma de a[l..r] (0-indexado, r inclusive): una resta, O(1)
long long suma(const vector<long long>& pre, int l, int r) { return pre[r + 1] - pre[l]; }
// 2D: P[i][j] = suma del rectángulo desde (0,0) hasta (i-1, j-1)
vector<vector<long long>> prefijos2d(const vector<vector<long long>>& g) {
int n = g.size(), m = g[0].size();
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] = g[i][j] + P[i][j+1] + P[i+1][j] - P[i][j];
return P;
}
// el rectángulo (r1,c1)..(r2,c2) inclusive son cuatro términos: el rectángulo grande,
// menos las dos franjas de más, más la esquina que se restó dos veces
long long suma_rect(const vector<vector<long long>>& P, int r1, int c1, int r2, int c2) {
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];
}Para nuestro arreglo, auto pre = prefijos(a) construye la tabla y
suma(pre, 2, 6) devuelve 13. Los límites deben satisfacer 0 <= l <= r < n.
Entender los cuatro términos en 2D
La función prefijos2d aplica la misma idea a rectángulos. Al sumar el prefijo
de arriba y el de la izquierda, la esquina superior izquierda aparece dos veces:
se resta una copia y se añade la celda actual.
Para consultar un rectángulo, el proceso se invierte:
| Paso | Región que usamos |
|---|---|
Sumar P[r2+1][c2+1] | todo hasta la esquina inferior derecha |
Restar P[r1][c2+1] | filas anteriores al rectángulo |
Restar P[r2+1][c1] | columnas anteriores al rectángulo |
Sumar P[r1][c1] | esquina que acabamos de restar dos veces |
Por ejemplo, en las filas [1,2,3] y [4,5,6], la columna central suma
P[2][2] - P[0][2] - P[2][1] + P[0][1] = 12 - 0 - 5 + 0 = 7.
La construcción cuesta O(filas × columnas), cada consulta O(1).
Esta implementación requiere una grilla no vacía y rectangular, con consultas válidas.
Qué cambia cuando modificamos los datos
Si a[4] pasa de 5 a 8, quedan desactualizados pre[5], pre[6], pre[7]
y pre[8]. Con muchas modificaciones, conviene guardar bloques más pequeños:
ese es el siguiente paso en Fenwick (BIT).
Para consultar mínimos, restar prefijos no permite recuperar lo que quitamos. Usa Sparse table (RMQ) si los datos son estáticos o Segment tree si cambian. Para sumar a rangos y consultar valores individuales, el arreglo de diferencias es otra técnica, desarrollada en 17 - Sumas de prefijos.
− pre[l]?
Consultar [2,6] daría 15 − 4 = 11: faltaría a[6], que vale 2.
pre[r]llega hasta la posición r − 1. El +1 de la fórmula incluye el extremo derecho; no es un ajuste arbitrario.