GEMPRO grupo de estudos para a maratona de programação

Tutorial

Soma de Prefixos

Técnica muito usada em problemas envolvendo somas em intervalos.

Nível: iniciante Autor: Miguel Oliveira

Introdução

Considere o seguinte problema:

Problema. Dado um array de nn inteiros (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n - 1}), você deve processar qq queries da seguinte forma: “dados inteiros ll, rr, calcule a soma al+al+1+⋯+ar−1a_l + a_{l + 1} + \dots + a_{r - 1}.”

Ou seja, o problema consiste em calcular a soma dos valores no intervalo [l,r)[l, r) do array.

Solução. Vamos calcular um array auxiliar

p=(0,a0,a0+a1,a0+a1+a2,… ) p = (0, a_0, a_0 + a_1, a_0 + a_1 + a_2, \dots)

de tamanho n+1n + 1. Em outras palavras,

pi=soma dos valores no prefixo de tamanho i do array p_i = \text{soma dos valores no prefixo de tamanho } i \text{ do array}

Agora, a soma al+al+1+⋯+ar−1a_l + a_{l + 1} + \dots + a_{r - 1} pode ser escrita como

(a0+a1+⋯+ar−1)−(a0+a1+⋯+al−1)=pr−pl (a_0 + a_1 + \dots + a_{r - 1}) - (a_0 + a_1 + \dots + a_{l - 1}) = p_r - p_l

Logo, as queries do problema podem ser respondidas em O(1)O(1) apenas calculando a diferença de dois elementos do array descrito acima. Esse array é chamado de “Soma de prefixos” (ou prefix sum).

Ideias

Soma de prefixos não precisa ser usada apenas para calcular a soma dos valores em um intervalo. Muitos problemas envolvendo somas em intervalos de um array podem ser simplificados se considerarmos o array de soma de prefixos, transformando um problema de somas de vários valores em um problema de diferença de dois valores.

A seguir alguns exemplos desse conceito.

Maior Soma de um intervalo

Problema. Dado um array (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n - 1}), encontre a maior soma possível de um intervalo do array.

Após transformar o problema em soma de prefixos, queremos calcular o maior valor possível de ar−ala_r - a_l com l<rl < r.

Basta iterar de 00 a nn no array de soma de prefixos, mantendo o menor valor encontrado até agora, e calculando a diferença pi−minp_i - min.

Contar intervalos com soma xx

Problema. Dado um array (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n - 1}) e um inteiro xx, calcule a quantidade de intervalos do array tais que a soma dos elementos é exatamente igual a xx.

Transformamos o problema em soma de prefixos, e basta contar a quantidade de pares (l,r)(l, r) tais que pr−pl=xp_r - p_l = x.

Podemos iterar pelo array de soma de prefixos da esquerda para a direita, mantendo a contagem de cada soma possível. Para cada posição ii, basta saber a quantidade de posições ll tais que pl=pi−xp_l = p_i - x até agora.

Problemas