Prefix Sum

O que e

Prefix sum e uma forma de precomputar a soma acumulada de um array.

Assim, em vez de somar um intervalo do zero toda vez, você responde usando diferença entre acumulados.

Quando usar

Ela aparece quando:

• existem muitas consultas de soma por faixa
• o array não muda o tempo todo
• você quer trocar preprocessamento por resposta rápida

Erro comum

O erro clássico e decorar a formula sem entender o ganho.

O ponto não e a formula.

O ponto e transformar várias somas O(n) em consultas O(1).

Pergunta melhor

Antes de aplicar, vale perguntar:

1. vou consultar muitos intervalos?
2. o custo de preprocessar vale a pena?
3. a estrutura muda tanto que o acumulado fica inutil?