Medio · sumas prefijas

Sumas por rangos 2D

El truco 1D era una resta. En dos dimensiones cada prefijo es un rectángulo, así que un subrectángulo exige restar dos franjas y devolver la esquina restada dos veces — un dibujo a mano vale más que la fórmula.

En una fraseConstruye <code>P[i][j]</code> = suma de las filas 1..i y columnas 1..j; cualquier rectángulo (r1,c1,r2,c2) es <code>P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]</code>.

El problema

Entrada: La primera línea trae n, m y q (1 ≤ n, m ≤ 50, 1 ≤ q ≤ 100). Luego n líneas con m enteros (0 ≤ a ≤ 1000). Después q líneas: r1 c1 r2 c2 (1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m).

Salida: q líneas: para cada consulta, la suma del rectángulo, una por línea.

Ejemplos:

Entrada	Salida
`2 2 3 1 2 3 4 1 1 2 2 1 1 1 1 2 2 2 2`	`10 1 4`

Primero las filas y luego las columnas — la misma convención que Sumar una matriz. Una sola celda (r1 = r2, c1 = c2) es un rectángulo válido, y también lo es la cuadrícula entera.

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 — Rellena la tabla con una fila y columna de ceros

Declara P[55][55] y deja la fila 0 y la columna 0 a ceros. Así la fórmula P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i][j] funciona con i = 1 y j = 1 sin casos especiales — el mismo truco que limpió la versión 1D.

Pista 2 — Dibuja las cuatro esquinas

Antes de memorizar la fórmula, dibuja dos rectángulos: el prefijo grande (1,1)-(r2,c2) y el deseado (r1,c1)-(r2,c2). Las dos franjas que hay que quitar están arriba y a la izquierda, y se solapan en la esquina superior izquierda — resta ambas y devuelve esa esquina una vez. Vista la imagen, la fórmula deja de ser un conjuro.

Pista 3 — La consulta reutiliza la construcción

La regla de construcción y la de consulta son la misma imagen leída en direcciones distintas: construir añade una celda a tres prefijos; consultar resta franjas de un prefijo grande. Si la construcción pasa los ejemplos pero las consultas fallan, el bug casi siempre está en los signos de las esquinas de la línea de consulta.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int P[55][55];

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

    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }

    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << endl;
    }
    return 0;
}

Ya tienes la versión 2D de pagar-una-vez-responder-muchas: la original 1D vive en Sumas por rangos, y esa exclusión de esquinas reaparecerá en problemas de conteo sobre cuadrículas. La lección que sobrevive a ambas: precalcula la estructura que implican las consultas y haz cada pregunta barata.

Análisis profundo

Por qué funciona

Define P[i][j] como el total de las filas 1..i y columnas 1..j. Cualquier rectángulo telescopa por inclusión-exclusión: el prefijo grande menos la franja de arriba menos la de la izquierda, más su esquina compartida (restada dos veces, se suma una). Construir y consultar son la misma imagen leída en direcciones opuestas.

El coste

O(n·m) en construir, O(1) por consulta, O(n·m) de espacio. Sumar cada rectángulo a mano cuesta O(n·m) por consulta: con q = 100 sobre una cuadrícula de 50×50 son 250.000 sumas frente a 100 restas.

Dónde falla

Olvidar + P[i-1][j-1] en la consulta — la esquina superior izquierda se restó dos veces y hay que sumarla una. Las consultas que tocan la fila 1 o la columna 1 esconden el bug (esas franjas son cero).
Reutilizar el array de la cuadrícula mientras construyes P: leer y P[i][j] += a sobre el mismo array 2D funciona, pero confundir índices (a[i][j] vs P[i-1][j-1]) por uno es la corrupción silenciosa clásica.
Orden fila/columna: el enunciado va por filas primero (n filas de m valores). Cambiarlo funciona por casualidad en ejemplos cuadrados y falla en los rectangulares.

Siguiente paso

El original 1D es Sumas por rangos — léelos juntos y la inclusión-exclusión se vuelve obvia. La siguiente estructura para cuadrículas es el array de diferencias 2D (modificaciones + consultas a la vez).

Dos cosas para recordar

P[i][j] = filas 1..i, cols 1..j; un rectángulo = grande − arriba − izquierda + esquina.
Rellena la fila 0 y la columna 0 con ceros y todas las fórmulas pierden sus casos especiales.

🐞 Esta versión falla: ábrela y pruébala

Pierde la esquina: el prefijo superior izquierdo se restó dos veces y nunca se devolvió

#include <iostream>
using namespace std;

int P[55][55];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }
    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] << endl;  // bug: no + corner
    }
    return 0;
}