Técnicas de Programação 03 - Somas de Prefixo

Escrito por Lúcio Figueiredo

A técnica de somas de prefixo é uma das mais recorrentes em olimpíadas de informática. Neste material, vamos definir as somas de prefixo e apresentar algumas de suas aplicações.

Motivação Inicial

Imagine o seguinte problema: Nos é dado um vetor v de tamanho n e q perguntas (ou queries). Cada query consiste de dois índices l e r. Para cada uma dessas queries, devemos imprimir como resposta a soma dos números de v com indíces entre l e r; ou seja, a resposta de cada query (l, r) é a soma v_l + v_{l+1} + ... + v_r.

Para resolver o problema, podemos utilizar uma solução bem simples: basta que percorramos o vetor com um loop for indo desde o índice l até o índice r, armazenando a soma dos valores em uma variável de resposta. Porém, note que a complexidade desta solução é O(n) para cada query; logo, a complexidade total da solução é O(n \cdot q). Para valores de n e q indo até 10^5, a solução realizará 10^{10} operações, o que não é eficiente. Como podemos resolver o problema com uma complexidade melhor?

Somas de Prefixo

Um prefixo de um vetor é definido como um intervalo contínuo deste vetor que começa do seu primeiro índice. Em particular, o i-ésimo prefixo do vetor v é o intervalo contínuo de elementos v_1, v_2, ..., v_i. Já uma soma de prefixo de um vetor é simplesmente a soma dos elementos de um prefixo. Ou seja, a i-ésima soma de prefixo do vetor v, denominada por s_i, é igual à soma v_1 + v_2 + ... + v_i.

Na imagem acima, podemos observar um exemplo de vetor v e cada uma de suas somas de prefixo. Para calcular as somas de prefixo s_i de um vetor v, podemos usar o seguinte simples algoritmo, com complexidade O(n):

  • Inicialmente, fazemos s_1 = v_1;
  • Em seguida, iteramos por cada índice i > 1 do vetor em sequência;
  • Para calcular s_i, basta fazer s_i = s_{i-1} + v_i. Ou seja, a soma dos i primeiros valores de v é igual à soma dos (i-1) primeiros valores somada ao valor do i-ésimo elemento.

Somas de intervalos em O(1)

Mas como somas de prefixo nos ajudam a encontrar a soma de um intervalo [l, r] qualquer? Observe que, utilizando somas de prefixo, conseguimos encontrar a soma do intervalo [1, r] - este valor é exatamente a soma s_r. Porém, esta soma inclui mais elementos do vetor do que o desejado; especificamente, a soma de prefixo s_r soma todos os elementos no intervalo [l, r] e, também, todos os elementos em [1, l-1]. Portanto, temos a seguinte relação:

s_r = v_1 + v_2 + ... + v_r = (v_1 + v_2 + ... + v_{l-1}) + (v_l + v_{l+1} + ... + v_r)

Porém, note que (v_1 + v_2 + ... + v_{l-1}) é exatamente igual a s_{l-1}! Logo, temos que

s_r = (v_1 + v_2 + ... + v_{l-1}) + (v_l + v_{l+1} + ... + v_r) = s_{l-1} + (v_l + v_{l+1} + ... + v_r)

\implies \boxed{(v_l + v_{l+1} + ... + v_r) = (s_r - s_{l-1})}

Ou seja, a soma do intervalo [l, r] é igual ao valor s_r - s_{l-1}. A imagem abaixo ilustra este fato de maneira intuitiva:

Portanto, utilizando somas de prefixos, conseguimos calcular somas de intervalos quaisquer de um vetor com complexidade O(1): basta imprimir o valor (s_r - s_{l-1}).

O código a seguir implementa a solução para o problema original indicada acima, utilizando somas de prefixos:

Problemas para praticar:

A lista a seguir contém alguns problemas que utilizam as ideias exploaradas na aula. Bons treinos!