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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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