Sumas prefijas en C#

Problema

El panel que suma cada vez

El panel de la tienda muestra los ingresos de un periodo elegido: «del día 120 al día 340», «los últimos 30 días», «esta semana frente a la semana pasada». Los gerentes lo abren muchas veces al día, y cada gráfico pregunta por docenas de periodos. El código suma de nuevo los días de cada periodo:

static long RangeSum(int[] revenue, int a, int b)
{
    long sum = 0;
    for (int day = a; day <= b; day++)
    {
        sum += revenue[day];
    }
    return sum;
}

Mil días de ingresos y mil consultas:

int[] revenue = RevenueOf(1000);
var queries = QueriesOf(1000);
long total = 0;
long additions = 0;
foreach (var (a, b) in queries)
{
    total += RangeSum(revenue, a, b);
    additions += b - a + 1;
}
Console.WriteLine($"consultas: {queries.Length}");
Console.WriteLine($"suma de las respuestas: {total}");
Console.WriteLine($"sumas: {additions}");

consultas: 1000
suma de las respuestas: 68412493
sumas: 248794

248 794 sumas para mil respuestas. Los días no cambian entre dos consultas, y aun así el código los suma una y otra vez. Cuanto más largos son los periodos y más consultas hay, más lento se vuelve el panel.

De dónde vienen los días y las consultas

Los ingresos y las consultas siguen una fórmula, para que los programas en los cuatro lenguajes y la comparación del navegador de más abajo construyan exactamente los mismos:

static int[] RevenueOf(int n)
{
    var revenue = new int[n];
    for (int i = 0; i < n; i++)
    {
        revenue[i] = 50 + (i * 37) % 451;
    }
    return revenue;
}

static (int A, int B)[] QueriesOf(int n)
{
    var queries = new (int A, int B)[n];
    for (int k = 0; k < n; k++)
    {
        int a = (k * 7919) % n;
        queries[k] = (a, a + (k * 4231) % (n - a));
    }
    return queries;
}

La idea

La suma de todo lo que hay a la izquierda

Calcula una vez, para cada día, los ingresos desde el principio hasta ese día. Esto es una suma prefija: prefix[k] es la suma de los primeros k días.

prefix[0] = 0: la suma de ningún día;
prefix[k + 1] = prefix[k] + revenue[k]: cada lugar es el anterior más un día.

El arreglo tiene un lugar más que días. Después, cada periodo es la diferencia de dos números. Los ingresos del día a al día b son los días 0 a b menos los días 0 a a − 1:

prefix[b + 1] − prefix[a]

Construirlo son n sumas, una vez. Cada consulta después son dos lecturas y una resta, sea el periodo de dos días o de dos años: O(1) por consulta en lugar de O(n).

Míralo

Las sumas prefijas, día a día

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

int[] revenue = { 120, 80, 150, 90, 200, 60, 110, 140 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"prefix: [{string.Join(", ", prefix)}]");
Console.WriteLine($"días 2–5: {RangeSum(prefix, 2, 5)}");

prefix: [0, 120, 200, 350, 440, 640, 700, 810, 950]
días 2–5: 500

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

Paso a paso, en palabras

8 días de ingresos. prefix tiene 9 lugares: prefix[0] = 0 es la suma de ningún día.
prefix[1] = prefix[0] + revenue[0] = 0 + 120 = 120: días 0–0.
prefix[2] = prefix[1] + revenue[1] = 120 + 80 = 200: días 0–1.
prefix[3] = prefix[2] + revenue[2] = 200 + 150 = 350: días 0–2.
prefix[4] = prefix[3] + revenue[3] = 350 + 90 = 440: días 0–3.
prefix[5] = prefix[4] + revenue[4] = 440 + 200 = 640: días 0–4.
prefix[6] = prefix[5] + revenue[5] = 640 + 60 = 700: días 0–5.
prefix[7] = prefix[6] + revenue[6] = 700 + 110 = 810: días 0–6.
prefix[8] = prefix[7] + revenue[7] = 810 + 140 = 950: días 0–7.
8 sumas, una vez. Ahora la consulta: los ingresos del día 2 al día 5. prefix[6] = 700 € son los días 0–5.
prefix[2] = 200 € son los días 0–1, la parte anterior al periodo. La quitamos.
700 − 200 = 500 €: los días 2–5 con dos lecturas y una resta, por largo que sea el periodo.
Construirlo cuesta n sumas una vez; cada consulta después cuesta una resta.

En la escena prefix[k] está en el límite entre el día k − 1 y el día k. Eso muestra que es la suma de todo lo que hay a la izquierda del límite, y que un periodo es la diferencia entre dos límites.

Más precisamente, para curiosos

Lo que te dan los lenguajes.

C# no tiene sumas prefijas ya hechas, ni en arreglos ni en LINQ. El bucle de arriba es la forma habitual.

Desbordamiento. prefix es long, no int. La última suma prefija son los ingresos de todo el periodo. En céntimos a lo largo de unos años supera 2 147 483 647, y un int entonces se convierte en silencio en un número negativo.

Pruébalo

Predice prefix

Tres días de ingresos: 30 €, 50 € y 20 €.

int[] revenue = { 30, 50, 20 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"prefix: [{string.Join(", ", prefix)}]");

Respuesta

prefix: [0, 30, 50, 20]

prefix: [0, 30, 80, 100]

prefix: [30, 80, 100]

Pruébalo

Completa

Los ingresos del día a al día b inclusive:

return prefix[] - prefix[a];

La idea

El cero delante

¿Por qué el arreglo tiene un lugar más? Se puede prescindir de él: prefix[k] podría ser la suma de los días 0 a k inclusive. Entonces el periodo de a a b es prefix[b] − prefix[a − 1]. Pero para a = 0 no existe el lugar a − 1, y cada consulta necesita una comprobación «si a es 0».

El cero delante elimina esa comprobación. El precio es un lugar en el arreglo, y la trampa es que los índices se desplazan en uno: prefix[k] es la suma de los días antes de k, no hasta k. Por eso un error de uno de más o de menos (off-by-one) es el fallo más común aquí, como en la búsqueda binaria.

Pruébalo

Encuentra el error

Alguien escribió las sumas prefijas sin el cero delante. La consulta de los días 2–5 debería dar 500 €:

int[] revenue = { 120, 80, 150, 90, 200, 60, 110, 140 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"días 2–5: {RangeSum(prefix, 2, 5)}");

días 2–5: 350

Elige la línea con el error.

Míralo

Mídelo: sumar de nuevo frente a las sumas prefijas

Las mismas mil consultas, con las sumas prefijas:

int[] revenue = RevenueOf(1000);
var queries = QueriesOf(1000);
long[] prefix = BuildPrefix(revenue);
long operations = revenue.Length;
long total = 0;
foreach (var (a, b) in queries)
{
    total += RangeSum(prefix, a, b);
    operations++;
}
Console.WriteLine($"consultas: {queries.Length}");
Console.WriteLine($"suma de las respuestas: {total}");
Console.WriteLine($"sumas y restas: {operations}");

consultas: 1000
suma de las respuestas: 68412493
sumas y restas: 2000

La suma de las respuestas es la misma, y el trabajo son 2000 operaciones en lugar de 248 794: mil sumas para prefix y una resta por consulta. Ejecuta las dos en el navegador. n es tanto el número de días como el número de consultas:

Volver a sumar en cada consulta O(n²)
Sumas de prefijos O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
Volver a sumar en cada consulta	10	248.794	≈ 2.487.940.000
Sumas de prefijos	20	2000	200.000

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

Sumar de nuevo es O(n) por consulta, O(n²) para n consultas. Con las sumas prefijas es O(n) una vez y O(1) por consulta. El precio es la memoria: un arreglo con n + 1 números.

Sumas prefijas bidimensionales: pedidos por día y hora

El mapa de calor de los pedidos es una tabla: las filas son días de la semana, las columnas son horas. La pregunta es «cuántos pedidos hay el martes y el miércoles de 10:00 a 13:00 h», es decir, la suma dentro de un rectángulo.

p[r][c] es la suma del rectángulo desde la esquina superior izquierda hasta la fila r − 1 y la columna c − 1, de nuevo con ceros delante (fila 0 y columna 0). Cada lugar es la celda más el rectángulo de arriba y el de la izquierda. La esquina entre ellos se contó dos veces, así que se resta una vez:

static int[,] BuildPrefix2D(int[,] orders)
{
    int rows = orders.GetLength(0);
    int cols = orders.GetLength(1);
    var p = new int[rows + 1, cols + 1];
    for (int r = 0; r < rows; r++)
    {
        for (int c = 0; c < cols; c++)
        {
            p[r + 1, c + 1] = orders[r, c] + p[r, c + 1] + p[r + 1, c] - p[r, c];
        }
    }
    return p;
}

static int Rect(int[,] 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];
}

int[,] orders = {
    { 3, 8, 12, 9, 5, 4 },
    { 2, 7, 14, 11, 6, 3 },
    { 4, 9, 15, 10, 7, 5 },
    { 1, 6, 11, 8, 4, 2 },
};
var p = BuildPrefix2D(orders);
Console.WriteLine($"pedidos mar–mié de 10 a 13 h: {Rect(p, 1, 1, 2, 3)}");

pedidos mar–mié de 10 a 13 h: 66

La consulta es la misma idea: todo el rectángulo hasta la esquina inferior derecha, menos la franja de arriba, menos la franja de la izquierda, más la esquina que se restó dos veces. Cuatro lecturas para un rectángulo de cualquier tamaño.

La idea

Cuántos periodos suman exactamente 50 €

La tienda tiene días con pérdida: los pedidos devueltos se descuentan de los ingresos. La pregunta es cuántos periodos de días consecutivos tienen una ganancia de exactamente 50 €.

Cada periodo del día i al día j es la diferencia de dos sumas prefijas: prefix[j + 1] − prefix[i]. Es 50 exactamente cuando prefix[i] = prefix[j + 1] − 50. Así que recorres los días, guardas la suma prefija actual y preguntas: ¿cuántas veces he visto hasta ahora una suma prefija igual a la actual menos 50? La respuesta se guarda en un mapa de suma prefija a cuántas veces se vio:

static int CountPeriods(int[] profit, int target)
{
    var seen = new Dictionary<int, int> { [0] = 1 };
    int prefix = 0;
    int count = 0;
    foreach (int p in profit)
    {
        prefix += p;
        count += seen.GetValueOrDefault(prefix - target);
        seen[prefix] = seen.GetValueOrDefault(prefix) + 1;
    }
    return count;
}

int[] profit = { 40, -10, 30, 20, -30, 50, -20, 30, 0, 20 };
Console.WriteLine($"periodos con 50 € de ganancia: {CountPeriods(profit, 50)}");

periodos con 50 € de ganancia: 8

Una pasada por los días y una búsqueda en una tabla hash por día: O(n). Dos bucles anidados sobre todos los periodos serían O(n²). El mapa aquí es un contador: cuántas veces se vio cada valor. Esa es una técnica aparte, y es el tema de la próxima lección.

Más precisamente, para curiosos

seen empieza con 0 → 1, porque la suma prefija antes del primer día es 0. Sin ella no se cuentan los periodos que empiezan el día 0.

Si todos los días dieran ganancia, también funcionaría una ventana deslizante: crecerla por la derecha mientras la suma sea menor que 50, reducirla por la izquierda cuando se pase. Con números negativos eso falla: reducir puede aumentar la suma, y la ventana no sabe en qué dirección ir. Las sumas prefijas con un mapa funcionan con cualquier número.

Pruébalo

Predice el conteo

Cuatro días de ganancia: 20 €, 30 €, −30 € y 30 €. ¿Cuántos periodos de días consecutivos suman exactamente 50 €?

int[] profit = { 20, 30, -30, 30 };
Console.WriteLine($"periodos con 50 € de ganancia: {CountPeriods(profit, 50)}");

Respuesta

periodos con 50 € de ganancia: 1

periodos con 50 € de ganancia: 3

periodos con 50 € de ganancia: 2

Ejercicio

El almacén, día a día

Resuelve la tarea en tu propio editor.

Entregado, vendido, en existencia. El almacén empieza con 40 unidades de un producto. Para diez días tienes dos arreglos:

entregado: 0, 25, 0, 30, 10, 0, 40, 0, 15, 0;
vendido: 12, 8, 15, 9, 20, 11, 7, 18, 10, 14.

Construye las sumas prefijas de ambos arreglos. Para los periodos días 2–5, 0–9 y 6–8 imprime cuánto se entregó, cuánto se vendió y las existencias al final del último día. Cada respuesta debe salir de unas pocas lecturas de las sumas prefijas, sin un bucle sobre los días.

días 2–5: entregados 40, vendidos 55, existencias al final 30
días 0–9: entregados 120, vendidos 124, existencias al final 36
días 6–8: entregados 55, vendidos 35, existencias al final 50

Más tareas

El pedido promedio en un periodo. Además de los ingresos tienes el número de pedidos por día. Un valor medio de pedido no se suma, pero las dos sumas sí. ¿Cómo respondes «el pedido promedio del día a al día b»?
La mejor semana. Con las sumas prefijas, encuentra los siete días consecutivos con mayores ingresos. ¿Cuántas operaciones necesita eso para 365 días?
El mapa de calor. Añade el viernes y el sábado a las sumas bidimensionales y encuentra la ventana de dos horas con más pedidos de toda la semana.

Test

Ponte a prueba

1. Los ingresos de cuatro días son 10 €, 20 €, 30 € y 40 €. ¿Qué es prefix?[10, 30, 60, 100][0, 10, 20, 30, 40][0, 10, 30, 60, 100]

2. ¿Cuál da los ingresos del día a al día b inclusive?prefix[b + 1] − prefix[a + 1]prefix[b] − prefix[a]prefix[b + 1] − prefix[a]

3. Los ingresos de ayer se corrigen por un pedido devuelto. ¿Qué pasa con prefix?Cambia cada lugar después de ese día: la corrección cuesta O(n)Cambia solo un lugarNada: prefix no depende de ayer

4. En countPeriods el mapa seen empieza con 0 → 1. ¿Por qué?Por los periodos que empiezan el día 0: para ellos buscamos la suma prefija 0 de antes del primer díaNo importa, solo aceleraPara que no esté vacío

Sumas prefijas

Cookies