Medio · sumas prefijas

Sumas por rangos

Sumar cada rango a mano cuesta O(longitud del rango) por pregunta, y las preguntas no dejan de llegar. Las sumas prefijas llevan todo el trabajo a una pasada de preparación: prefix[i] es la suma de los i primeros números, así que cualquier rango es una resta.

En una fraseConstruye una vez <code>prefix[i] = prefix[i-1] + a[i]</code> para i = 1..n. La respuesta de [l, r] es <code>prefix[r] - prefix[l-1]</code>: una resta por consulta, con <code>long long</code> para totales de 10^13.

El problema

Entrada: La primera línea trae n y q (1 ≤ n ≤ 10000, 1 ≤ q ≤ 10000). La segunda, n enteros (−10^9 ≤ a_i ≤ 10^9). Luego q líneas con l y r (1 ≤ l ≤ r ≤ n).

Salida: q líneas: para cada consulta, la suma de a[l..r], una por línea.

Ejemplos:

EntradaSalida
5 3
1 2 3 4 5
1 5
2 4
3 3		15
9
3

La convención de empezar en 1 trabaja en silencio aquí: prefix[0] = 0 hace que la fórmula funcione con l = 1 sin casos especiales. El error de uno vive justo en esa costura — mira el ejemplo fallido de abajo.

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Haz que prefix[i] incluya a[i]

Fija el significado prefix[i] = a[1] + … + a[i] y pon prefix[0] = 0. Entonces la suma de a[l..r] telescopa: todo hasta r, menos todo lo anterior a l. La mitad de los errores de uno en este problema vienen de mezclar las dos convenciones.

Pista 2 — El array va de 1, C++ de 0

Declara los arrays una casilla más grandes e ignora la casilla 0 (o guarda ahí el 0), para que a[1..n] y prefix[1..n] queden en sus índices naturales. Pelear con la convención a base de - 1 regados por el código es como nacen los errores de signo.

Pista 3 — int no cabe ahí

Cada elemento cabe en un int (hasta 10^9), pero n de ellos suman 10^13: muy por encima del techo de int, unos 2.1 × 10^9. Declara prefix como array de long long. El desbordamiento no revienta: devuelve un número equivocado en silencio, que es el peor tipo de bug.

Solución (¡inténtalo primero!) 
#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;

    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
    return 0;
}

Las sumas prefijas son la primera estructura que construyes antes de conocer las preguntas — y la misma idea vuelve en Suma máxima de subarray, donde una diferencia de prefijos encuentra la mejor ventana en una pasada. Cuando a las consultas se suman modificaciones, la siguiente herramienta es el array de diferencias; después, los árboles.

Análisis profundo

Por qué funciona

Guarda el total acumulado. prefix[r] - prefix[l-1] cancela todo lo que los dos prefijos comparten y deja exactamente a[l] + … + a[r]. Es el mismo telescopado que hace rápidos los cubos de la criba y del counting sort: construye una estructura y responde con diferencias.

El coste

O(n) en construir, O(1) por consulta, O(n) de espacio. La fuerza bruta sería O(n·q): con n = q = 10000 son 100 millones de sumas frente a 20 mil.

Dónde falla

  • Responder prefix[r] - prefix[l] — se come a[l] en silencio. La fórmula es prefix[l-1], y los tests que solo usan l = 1 esconden el bug.
  • Guardar prefix en int: cada elemento cabe, el total no. El desbordamiento da la vuelta en silencio y las respuestas solo parecen plausibles.

Siguiente paso

El truco del total acumulado vuelve como la intuición de Kadane en Suma máxima de subarray — la mejor ventana es una diferencia de dos prefijos.

Dos cosas para recordar

  • prefix[i] = a[1] + … + a[i]; un rango es prefix[r] − prefix[l−1].
  • Sumar muchos int exige long long — el desbordamiento avisa poco.
🐞 Esta versión falla: ábrela y pruébala

Responde prefix[r] - prefix[l]: se come a[l] sin decir nada

#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l] << endl;
    }
    return 0;
}