Sumas de prefijos y arreglos de diferencias en C#

La ventana deslizante de la parte 2 venía con una condición: agrandar la ventana tenía que significar agrandar la cantidad. Basta un número negativo para que eso deje de ser cierto, y todo el patrón se derrumba.

A las sumas de prefijos eso no les importa. Pagas una vez por adelantado, y después cada pregunta sobre un rango es una resta.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la corrida.

La compensación

Console.WriteLine($"{"n",9}  {"queries",9}  {"scan each",16}  {"prefix",12}");

foreach ((int n, int q) in new[] { (10, 5), (1_000, 1_000), (200_000, 200_000) })
{
    long scan = (long)q * n;          // worst case: every query spans the array
    long prefix = n + q;              // build once, then O(1) per query
    Console.WriteLine($"{n,9:N0}  {q,9:N0}  {scan,16:N0}  {prefix,12:N0}");
}

Imprime:

        n    queries         scan each        prefix
       10          5                50            15
    1,000      1,000         1,000,000         2,000
  200,000    200,000    40,000,000,000       400,000

Cuarenta mil millones contra cuatrocientos mil. Esa es la forma de todos los patrones de esta parte: haz el trabajo lineal una sola vez, y después responde cada pregunta en O(1).

Patrón 11 — La suma de prefijos

pre[i] guarda la suma de todo lo que está antes del índice i. El arreglo tiene n+1 celdas, no n, y la celda extra hace trabajo real.

int[] a = [3, 1, 4, 1, 5, 9, 2, 6];

// pre[i] is the sum of the first i values, so pre[0] is 0 and pre.Length is n+1.
int[] pre = new int[a.Length + 1];
for (int i = 0; i < a.Length; i++) pre[i + 1] = pre[i] + a[i];

Console.WriteLine($"a   = [{string.Join(", ", a)}]");
Console.WriteLine($"pre = [{string.Join(", ", pre)}]");
Console.WriteLine();

foreach ((int lo, int hi) in new[] { (0, 2), (2, 5), (5, 7), (0, 7) })
{
    int sum = pre[hi + 1] - pre[lo];
    Console.WriteLine($"sum a[{lo}..{hi}] = pre[{hi + 1}] - pre[{lo}] = {pre[hi + 1]} - {pre[lo]} = {sum,2}   " +
                      $"[{string.Join(", ", a[lo..(hi + 1)])}]");
}

Imprime:

a   = [3, 1, 4, 1, 5, 9, 2, 6]
pre = [0, 3, 4, 8, 9, 14, 23, 25, 31]

sum a[0..2] = pre[3] - pre[0] = 8 - 0 =  8   [3, 1, 4]
sum a[2..5] = pre[6] - pre[2] = 23 - 4 = 19   [4, 1, 5, 9]
sum a[5..7] = pre[8] - pre[5] = 31 - 14 = 17   [9, 2, 6]
sum a[0..7] = pre[8] - pre[0] = 31 - 0 = 31   [3, 1, 4, 1, 5, 9, 2, 6]

Lo que hay que entender bien es que pre se indexa por fronteras, no por elementos. pre[2] no es “el valor en el índice 2” — es “todo lo que está antes del índice 2”. Una vez que lo ves así, la fórmula del rango deja de tener que memorizarse:

sum a[lo..hi]  =  pre[hi + 1] - pre[lo]

Y pre[0] = 0, el prefijo vacío, es lo que permite que un rango que empieza en el índice 0 funcione sin ningún caso especial. Construye pre con n celdas en vez de n+1 y vas a escribir ese caso especial, lo vas a equivocar por poco, y vas a perder veinte minutos.

Costo: O(n) para construirlo, O(1) por consulta, O(n) de espacio.

Úsalo cuando hay muchas consultas de rango sobre datos que no cambian. Si los datos sí cambian entre consultas, lo que quieres es un árbol de Fenwick o un árbol de segmentos — una suma de prefijos hay que reconstruirla desde la edición en adelante.

Patrón 12 — Sumas de prefijos más un diccionario

Cuenta los subarreglos que suman un objetivo, permitiendo valores negativos.

Aquí está el cambio de enfoque. Un subarreglo a[lo..hi] suma target justo cuando pre[hi+1] - pre[lo] == target, que se reordena a pre[lo] == pre[hi+1] - target. Así que recorre el arreglo llevando el total acumulado, y en cada paso pregunta: ¿he visto antes el prefijo running - target, y cuántas veces?

// Negative values, so no sliding window can solve this: growing the window
// no longer means growing the sum.
int[] a = [3, 4, 7, -2, 2, 1, 4, 2];
int target = 7;

Dictionary<int, int> seen = new() { [0] = 1 };   // one empty prefix, sum 0
int running = 0, found = 0;

for (int i = 0; i < a.Length; i++)
{
    running += a[i];
    int need = running - target;
    int hits = seen.GetValueOrDefault(need);

    if (hits > 0)
        Console.WriteLine($"i={i}  running={running,2}  looking for {need,2}  found {hits}x  -> {hits} subarray(s) ending here");
    else
        Console.WriteLine($"i={i}  running={running,2}  looking for {need,2}  none");

    found += hits;
    seen[running] = seen.GetValueOrDefault(running) + 1;
}

Console.WriteLine($"\nsubarrays summing to {target}: {found}");

Imprime:

i=0  running= 3  looking for -4  none
i=1  running= 7  looking for  0  found 1x  -> 1 subarray(s) ending here
i=2  running=14  looking for  7  found 1x  -> 1 subarray(s) ending here
i=3  running=12  looking for  5  none
i=4  running=14  looking for  7  found 1x  -> 1 subarray(s) ending here
i=5  running=15  looking for  8  none
i=6  running=19  looking for 12  found 1x  -> 1 subarray(s) ending here
i=7  running=21  looking for 14  found 2x  -> 2 subarray(s) ending here

subarrays summing to 7: 6

Dos cosas sostienen esto.

seen se inicializa con {0: 1} antes de que empiece el bucle. Esa entrada representa el prefijo vacío, y sin ella se te escapa todo subarreglo que empiece en el índice 0 — incluido, aquí, el [3, 4] en i=1. Es el error más común del patrón, y solo aparece cuando la respuesta justo empieza al principio.

El diccionario cuenta apariciones en vez de guardar una bandera, porque el mismo prefijo puede aparecer muchas veces y cada una es un subarreglo distinto. Mira i=7: el prefijo 14 ya se había visto dos veces, así que ahí terminan dos subarreglos.

Costo: O(n) de tiempo, O(n) de espacio.

Úsalo cuando el arreglo tiene números negativos y estabas por usar una ventana deslizante. Este es el patrón que la reemplaza.

Patrón 13 — El arreglo de diferencias

Ahora córrelo al revés. Tienes actualizaciones de rango que aplicar — suma 3 a todo lo que está entre el índice 2 y el 5 — y son muchas, y solo necesitas el arreglo final al terminar.

Aplicar cada actualización elemento por elemento es O(rango) cada vez. En vez de eso, registra solo dónde empieza cada actualización y dónde termina:

d[lo]      += v      // from here on, add v
d[hi + 1]  -= v      // from here on, stop adding it

Dos escrituras, sea cual sea el largo del rango. Después una pasada de suma de prefijos sobre d convierte las marcas de vuelta en valores.

int n = 6;
int[] diff = new int[n + 1];       // one extra cell, so hi+1 is always in range

(int lo, int hi, int v)[] updates = [(1, 3, +2), (2, 5, +3), (0, 2, -1)];

foreach ((int lo, int hi, int v) in updates)
{
    diff[lo] += v;
    diff[hi + 1] -= v;
    Console.WriteLine($"add {v,2} to [{lo}..{hi}]   diff[{lo}] {v:+#;-#;0}, diff[{hi + 1}] {-v:+#;-#;0}   " +
                      $"-> [{string.Join(", ", diff)}]");
}

int[] final = new int[n];
int running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; final[i] = running; }

Console.WriteLine($"\nrunning sum of diff -> [{string.Join(", ", final)}]");

// Brute force, to prove it.
int[] check = new int[n];
foreach ((int lo, int hi, int v) in updates)
    for (int i = lo; i <= hi; i++) check[i] += v;
Console.WriteLine($"element by element   -> [{string.Join(", ", check)}]");
Console.WriteLine($"same: {final.SequenceEqual(check)}");

Imprime:

add  2 to [1..3]   diff[1] +2, diff[4] -2   -> [0, 2, 0, 0, -2, 0, 0]
add  3 to [2..5]   diff[2] +3, diff[6] -3   -> [0, 2, 3, 0, -2, 0, -3]
add -1 to [0..2]   diff[0] -1, diff[3] +1   -> [-1, 2, 3, 1, -2, 0, -3]

running sum of diff -> [-1, 1, 4, 5, 3, 3]
element by element   -> [-1, 1, 4, 5, 3, 3]
same: True

La comprobación por fuerza bruta del final está ahí porque este parece que no debería funcionar.

d se reserva con n + 1 celdas para que d[hi + 1] esté en rango cuando hi es el último índice. La reconstrucción nunca lee esa última celda — existe solo para que la escritura de “deja de sumar” siempre tenga a dónde ir.

Costo: O(1) por actualización, O(n) una sola vez al final.

Úsalo cuando el problema son m actualizaciones de rango seguidas de leer el resultado — sistemas de reservas, conteo de asientos de vuelos, “cuántos intervalos cubren cada punto”. Si las actualizaciones y las consultas se intercalan, necesitas un árbol de Fenwick.

Patrón 14 — Dos dimensiones

La misma idea, un eje más. pre[r][c] guarda la suma de todo lo que está estrictamente arriba de la fila r y estrictamente a la izquierda de la columna c.

Construirlo necesita inclusión–exclusión, y consultarlo también. La región de la esquina pertenece tanto a la franja de arriba como a la franja de la izquierda, así que restar las dos la quita dos veces.

int[,] g = {
    {  1,  2,  3,  4 },
    {  5,  6,  7,  8 },
    {  9, 10, 11, 12 },
    { 13, 14, 15, 16 },
};
int rows = g.GetLength(0), cols = g.GetLength(1);

// pre[r, c] = sum of everything strictly above row r and left of column c.
int[,] pre = new int[rows + 1, cols + 1];
for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
        pre[r + 1, c + 1] = g[r, c] + pre[r, c + 1] + pre[r + 1, c] - pre[r, c];

Console.WriteLine("pre:");
for (int r = 0; r <= rows; r++)
{
    for (int c = 0; c <= cols; c++) Console.Write($"{pre[r, c],5}");
    Console.WriteLine();
}

int Query(int r1, int c1, int r2, int c2) =>
    pre[r2 + 1, c2 + 1] - pre[r1, c2 + 1] - pre[r2 + 1, c1] + pre[r1, c1];

Console.WriteLine();
foreach ((int r1, int c1, int r2, int c2) in new[] { (1, 1, 2, 2), (0, 0, 1, 1), (2, 0, 3, 3) })
{
    int brute = 0;
    for (int r = r1; r <= r2; r++) for (int c = c1; c <= c2; c++) brute += g[r, c];
    Console.WriteLine($"rows {r1}..{r2}, cols {c1}..{c2}  ->  {Query(r1, c1, r2, c2),3}   (brute force {brute,3})");
}

Imprime:

pre:
    0    0    0    0    0
    0    1    3    6   10
    0    6   14   24   36
    0   15   33   54   78
    0   28   60   96  136

rows 1..2, cols 1..2  ->   34   (brute force  34)
rows 0..1, cols 0..1  ->   14   (brute force  14)
rows 2..3, cols 0..3  ->  100   (brute force 100)

Tanto la construcción como la consulta usan la misma forma + - - +, y la usan por la misma razón. Si solo puedes recordar una cosa, recuerda que el último término es un más y es la esquina que quitaste dos veces.

Costo: O(rows × cols) para construirlo, O(1) por consulta.

Úsalo cuando las consultas son rectángulos en una cuadrícula. Problemas de imágenes, sumas de matrices, y cualquier pregunta del tipo “cuenta las cosas dentro de esta caja”.

Patrón 15 — XOR de prefijos

XOR se parece lo bastante a la suma como para que todo esto se traslade, porque es su propio inverso: x ^ y ^ y == x. Así que el truco del prefijo funciona con ^ en lugar de +, y la resta se vuelve otro ^.

El reordenamiento es el único paso que vale la pena mirar despacio:

running ^ need == target      // what we want
need == running ^ target      // xor both sides by running

int[] a = [4, 2, 2, 6, 4];
int target = 6;

Dictionary<int, int> seen = new() { [0] = 1 };
int running = 0, found = 0;

for (int i = 0; i < a.Length; i++)
{
    running ^= a[i];
    int need = running ^ target;          // because x ^ need == target  =>  need == x ^ target
    int hits = seen.GetValueOrDefault(need);
    found += hits;

    Console.WriteLine($"i={i}  a[i]={a[i]}  prefixXor={running}  need={need}  matches={hits}");
    seen[running] = seen.GetValueOrDefault(running) + 1;
}

Console.WriteLine($"\nsubarrays with XOR {target}: {found}");

int brute = 0;
for (int i = 0; i < a.Length; i++)
{
    int x = 0;
    for (int j = i; j < a.Length; j++) { x ^= a[j]; if (x == target) brute++; }
}
Console.WriteLine($"brute force:            {brute}");

Imprime:

i=0  a[i]=4  prefixXor=4  need=2  matches=0
i=1  a[i]=2  prefixXor=6  need=0  matches=1
i=2  a[i]=2  prefixXor=4  need=2  matches=0
i=3  a[i]=6  prefixXor=2  need=4  matches=2
i=4  a[i]=4  prefixXor=6  need=0  matches=1

subarrays with XOR 6: 4
brute force:            4

Estructuralmente idéntico al patrón 12 — el mismo diccionario inicializado, el mismo conteo — con + cambiado por ^. Ese es el punto de incluirlo: cuando ves las sumas de prefijos como “cualquier operación con un inverso”, la familia se vuelve mucho más grande que la suma.

Costo: O(n) de tiempo, O(n) de espacio.

Úsalo cuando el problema es sobre XOR de rangos. También se generaliza a productos, si tienes cuidado con los ceros, y a cualquier operación asociativa con un inverso.

Qué recordar

• pre se indexa por fronteras, no por elementos. n+1 celdas, pre[0] = 0, y sum a[lo..hi] = pre[hi+1] - pre[lo] sin ningún caso especial al principio.

• Las sumas de prefijos son lo que usas cuando una ventana deslizante no funciona. En cuanto aparecen los negativos, agrandar la ventana deja de significar agrandar la suma, y la ventana se queda sin nada de qué agarrarse.

• Inicializa el diccionario con {0: 1}. Es el prefijo vacío. Si lo dejas fuera, desaparece toda respuesta que empiece en el índice 0 — incluso con entradas donde nada más se ve mal.

• Cuenta apariciones en el diccionario, no presencia. Que el mismo prefijo se repita es el mismo objetivo alcanzado otra vez.

• Un arreglo de diferencias convierte una actualización de rango en dos escrituras. d[lo] += v, d[hi+1] -= v, y después una pasada. Reserva n+1 celdas para que la segunda escritura siempre caiga en algún lado.

• En 2D, el último término de la consulta es un más. La esquina se restó dos veces: una por la franja de arriba y otra por la franja de la izquierda.

• En realidad no se trata de la suma. Sirve cualquier operación con un inverso, y por eso la versión con XOR es el mismo código con un carácter cambiado.

La parte 4 es búsqueda binaria, y en concreto los dos tercios de ella que no son “encuentra este elemento en un arreglo ordenado”.