Somas de prefixos e arrays de diferenças em C#

A janela deslizante da parte 2 vinha com uma condição: crescer a janela tinha que significar crescer a quantidade. Basta um número negativo para isso deixar de ser verdade, e o padrão inteiro desmorona.

Somas de prefixos não se importam. Você paga uma vez adiantado, e toda pergunta sobre um intervalo depois disso é uma subtração.

Todo programa abaixo está completo, foi rodado no .NET 10, e a saída está colada da execução.

A troca

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}");
}

Ele 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

Quarenta bilhões contra quatrocentos mil. É essa a forma de todo padrão desta parte: faça o trabalho linear uma vez, depois responda cada pergunta em O(1).

Padrão 11 — A soma de prefixos

pre[i] guarda a soma de tudo antes do índice i. O array tem n+1 células, não n, e a célula extra faz trabalho de verdade.

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)])}]");
}

Ele 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]

O que você precisa acertar é que pre é indexado por fronteiras, não por elementos. pre[2] não é “o valor no índice 2” — é “tudo antes do índice 2”. Quando você segura a ideia assim, a fórmula do intervalo para de precisar ser decorada:

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

E pre[0] = 0, o prefixo vazio, é o que deixa um intervalo que começa no índice 0 funcionar sem caso especial. Construa pre com n células em vez de n+1 e você vai escrever esse caso especial, errar sutilmente, e perder vinte minutos.

Custo: O(n) para construir, O(1) por consulta, O(n) de espaço.

Use quando há muitas consultas de intervalo sobre dados que não mudam. Se os dados mudam entre consultas, o que você quer é uma Fenwick tree ou uma segment tree — uma soma de prefixos tem que ser reconstruída da edição em diante.

Padrão 12 — Somas de prefixos mais um hash map

Conte os subarrays que somam um alvo, com valores negativos permitidos.

Aqui está a reformulação. Um subarray a[lo..hi] soma target exatamente quando pre[hi+1] - pre[lo] == target, que se reorganiza em pre[lo] == pre[hi+1] - target. Então percorra o array mantendo o total acumulado, e a cada passo pergunte: já vi o prefixo running - target antes, e quantas vezes?

// 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}");

Ele 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

Duas coisas sustentam isto.

seen é inicializado com {0: 1} antes do laço começar. Essa entrada representa o prefixo vazio, e sem ela todo subarray que começa no índice 0 é perdido — inclusive, aqui, o [3, 4] em i=1. É o bug mais comum do padrão, e só aparece quando a resposta por acaso começa no início.

O map conta ocorrências em vez de guardar um flag, porque o mesmo prefixo pode aparecer muitas vezes e cada uma é um subarray diferente. Olhe o i=7: o prefixo 14 tinha sido visto duas vezes, então dois subarrays terminam ali.

Custo: O(n) de tempo, O(n) de espaço.

Use quando o array tem números negativos e você ia pegar uma janela deslizante. Este é o padrão que a substitui.

Padrão 13 — O array de diferenças

Agora rode ao contrário. Você tem atualizações de intervalo para aplicar — some 3 a tudo entre o índice 2 e o 5 — e muitas delas, e só precisa do array final no fim.

Aplicar cada atualização elemento por elemento é O(tamanho do intervalo) toda vez. Em vez disso, registre só onde cada atualização começa e onde ela para:

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

Duas escritas, seja qual for o tamanho do intervalo. Depois uma passada de soma de prefixos sobre d transforma as marcas de volta em 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)}");

Ele 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

A verificação por força bruta no fim está ali porque este aqui parece que não deveria funcionar.

d é alocado com n + 1 células para que d[hi + 1] esteja no intervalo quando hi é o último índice. Essa última célula nunca é lida pela reconstrução — ela existe só para que a escrita de “pare de somar” sempre tenha onde cair.

Custo: O(1) por atualização, O(n) uma vez no fim.

Use quando o problema é m atualizações de intervalo seguidas de ler o resultado — sistemas de reserva, contagem de assentos de voo, “quantos intervalos cobrem cada ponto”. Se atualizações e consultas se intercalam, você precisa de uma Fenwick tree.

Padrão 14 — Duas dimensões

Mesma ideia, mais um eixo. pre[r][c] guarda a soma de tudo estritamente acima da linha r e estritamente à esquerda da coluna c.

Construir isso precisa de inclusão–exclusão, e consultar também. A região do canto pertence tanto à faixa de cima quanto à faixa da esquerda, então subtrair as duas a remove duas vezes.

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})");
}

Ele 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 a construção quanto a consulta usam a mesma forma + - - +, e pelo mesmo motivo. Se você só puder lembrar de uma coisa, lembre que o último termo é um mais e que é o canto que você tirou duas vezes.

Custo: O(linhas × colunas) para construir, O(1) por consulta.

Use quando as consultas são retângulos numa grade. Problemas de imagem, somas de matrizes, e qualquer pergunta do tipo “conte as coisas dentro desta caixa”.

Padrão 15 — XOR de prefixos

XOR se comporta parecido o bastante com a adição para tudo isto continuar valendo, porque ele é seu próprio inverso: x ^ y ^ y == x. Então o truque do prefixo funciona com ^ no lugar de +, e a subtração vira outro ^.

A reorganização é o único passo que vale a pena ir devagar:

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}");

Ele 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

Estruturalmente idêntico ao padrão 12 — mesmo map inicializado, mesma contagem — com + trocado por ^. É por isso que ele está aqui: quando você vê somas de prefixos como “qualquer operação com um inverso”, a família fica bem maior que a adição.

Custo: O(n) de tempo, O(n) de espaço.

Use quando o problema é sobre XOR de intervalos. Também generaliza para produtos, se você tomar cuidado com zeros, e para qualquer operação associativa com um inverso.

O que lembrar

• pre é indexado por fronteiras, não por elementos. n+1 células, pre[0] = 0, e sum a[lo..hi] = pre[hi+1] - pre[lo] sem caso especial no começo.

• Somas de prefixos são o que você usa quando uma janela deslizante não funciona. No momento em que aparecem negativos, crescer a janela para de significar crescer a soma, e a janela não tem em que se segurar.

• Inicialize o map com {0: 1}. É o prefixo vazio. Deixe de fora e toda resposta que começa no índice 0 desaparece — inclusive em entradas onde nada mais parece errado.

• Conte ocorrências no map, não presença. O mesmo prefixo se repetindo é o mesmo alvo atingido de novo.

• Um array de diferenças transforma uma atualização de intervalo em duas escritas. d[lo] += v, d[hi+1] -= v, depois uma passada. Aloque n+1 células para a segunda escrita sempre ter onde cair.

• Em 2D, o último termo da consulta é um mais. O canto foi subtraído duas vezes, pela faixa de cima e pela faixa da esquerda.

• Não é realmente sobre adição. Qualquer operação com um inverso funciona, e é por isso que a versão XOR é o mesmo código com um caractere trocado.

A parte 4 é busca binária, e especificamente os dois terços dela que não são “encontre este elemento num array ordenado”.