Feito por Thiago Mota
Imagine o seguinte problema, dado um vetor de $$N$$ elementos e $$Q$$ intervalos $$[l, r]$$ queremos saber para cada uma das $$Q$$ perguntas a soma dos elementos da posição $$l$$ até $$r$$ no vetor.
A solução mais fácil seria andar pelo vetor de $$l$$ até $$r$$ para cada uma das perguntas:
https://gist.github.com/Thiago4532/609d652282edcd7ac3c0ea3cf1245405
Sendo que isso fica em uma complexidade de $$O(N \cdot Q)$$, que para valores de $$10^5$$ receberia um TLE.
A solução rápida seria utilizando soma de prefixos, vamos olhar para o seguinte vetor: $$v = [2, 1, 3, 4, 7, 5, 3]$$, para resolver o problema da soma iremos definir um vetor de prefixo $$pref$$ de forma que $$pref(i)$$ vai guardar a soma de todos os elementos em $$v$$ de $$1$$ até $$i$$, no caso desse vetor o prefixo ficaria assim: $$pref = [2, 3, 6, 10, 17, 22, 25]$$, com esse vetor de prefixo podemos responder qualquer pergunta em um intervalo de $$[1, i]$$, mas caso olharmos para a soma da posição $$[3, 5]$$ podemos imaginar como sendo a soma de $$[1, 5]$$ menos a soma de $$[1, 2]$$, ou seja, utilizando o vetor de prefixo podemos calcular a soma para qualquer intervalo $$[l, r]$$, segue um exemplo:
$$v = [\textbf{2}, \textbf{1}, \textbf{3}, \textbf{4},\textbf{7}, 5, 3]$$ ($$soma = 17$$)
$$v = [\textbf{2}, \textbf{1}, 3, 4, 7, 5, 3]$$ ($$soma = 3$$)
$$v = [2, 1, \textbf{3}, \textbf{4},\textbf{7} , 5, 3]$$ ($$soma = 17-3$$)
Resumindo, para calcular a soma de $$[l, r]$$ podemos calcular a soma de $$[1, r]$$ e subtrair da soma de $$[1, l-1]$$, e para calcular essa soma podemos fazer $$pref(r) – pref(l-1)$$, segue o código:
https://gist.github.com/Thiago4532/a191eb0d7dc21468c22d5a275c08efe6
A ideia de prefixo pode ser utilizada para multiplicação (utilizando divisão como operação oposta) ou qualquer outra operação que possua um inverso.
Exercícios para praticar:
OBI 2017 P1 – Segredo do Cofre