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:
| // Ideias 06 – Soma de Prefixos | |
| // Thiago Mota | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 100010; | |
| int n, q, v[maxn]; | |
| int main() { | |
| cin >> n >> q; | |
| for(int i = 1; i <= n; i++) { | |
| cin >> v[i]; // Lendo o vetor | |
| } | |
| for(int i = 1; i <= q; i++) { | |
| int l, r; | |
| cin >> l >> r; | |
| int soma = 0; | |
| for(int j = l; j <= r; j++) | |
| soma += v[j]; // Somando cada elemento de [l, r] | |
| cout << soma << "\n"; | |
| } | |
| return 0; | |
| } |
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:
| // Ideias 06 – Soma de Prefixos | |
| // Thiago Mota | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 100010; | |
| int n, q, v[maxn], pref[maxn]; | |
| int main() { | |
| cin >> n >> q; | |
| for(int i = 1; i <= n; i++) { | |
| cin >> v[i]; // Lendo o vetor | |
| } | |
| pref[1] = v[1]; // Prefixo da posição 1 é ele mesmo | |
| for(int i = 2; i <= n; i++) { | |
| pref[i] = pref[i-1] + v[i]; // O prefixo de i é o prefixo de i-1 adicionado do elemento na posição i | |
| } | |
| for(int i = 1; i <= q; i++) { | |
| int l, r; | |
| cin >> l >> r; | |
| if(l == 1) { | |
| cout << pref[r] << "\n"; // Se o l for 1, podemos apenas imprimir o prefixo. | |
| }else { | |
| cout << pref[r] – pref[l-1] << "\n"; // Senão, iremos imprimir a soma de [1, r] – [1, l-1] | |
| } | |
| } | |
| return 0; | |
| } |
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
