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!