🧱 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.

3011422354052617pre[7]17− pre[2]− 4queda= 13

Si el diagrama no cabe, deslízalo horizontalmente.

i: cantidad de elementos incluidos012345678
pre[i]03481015151718

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ónTiempoRazón
ConstruirO(n)una suma por elemento
Consultar un intervaloO(1)dos accesos y una resta
Cambiar un elemento y mantener los prefijosO(n) en el peor casomodifica todos los prefijos que lo incluyen
Memoria adicionalO(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:

PasoRegió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.