Aula por Pedro Victor
Soma de Prefixos é uma técnica para saber a soma de um intervalo entre dois índices $[l,r]$ de algum vetor de maneira mais rápida. Digamos que temos um vetor $V$ com $N$ elementos e também temos $M$ perguntas sobre a soma do intervalo entre $l$ e $r$. Sendo assim, a solução mais simples seria ir somando todos os números de $l$ a $r$, como no exemplo abaixo:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int v[1000000]; | |
| int n,m; | |
| int main() | |
| { | |
| cin >> n >> m; //Quantidade de elementos no vetor v e a quantidade de perguntas m | |
| for(int i = 1 ; i <= n ; i++) | |
| { | |
| cin >> v[i]; //O número na posição i do vetor | |
| } | |
| for(int i = 1; i <= m ; i++) | |
| { | |
| int l,r; //O intervalo de l até r | |
| cin >> l >> r; | |
| //Percorro esse intervalo somando todos os elementos em uma variavel resposta | |
| int resposta = 0; | |
| for(int j = l ; j <= r ; j++) | |
| { | |
| resposta = resposta + v[j]; | |
| } | |
| cout << "No intervalo de" << l << " ate " << r << " a soma e " << resposta << "\n"; | |
| } | |
| return 0; | |
| } |
Porém, dessa maneira, a complexidade seria $O(N*M)$, podendo exceder o limite de tempo na maioria dos casos. Para otimizar esse código, devemos usar a Soma de Prefixos.
Primeiro temos um vetor com os elementos $V = (1,3,2,4,9,8,1)$ e utilizaremos um vetor auxiliar (chamaremos de $aux$) para guardar a soma de todos os elementos de $1$ até $i$, isto é, o prefixo de $i$. Neste caso, ficaria $aux = (1,4,6,10,19,27,28)$. Para saber o intervalo $[l,r]$, simplesmente iríamos pegar a soma do intervalo $[1,r]$ (ou seja, o prefixo de $r$) e diminuir dela o prefixo de $l-1$. Por exemplo, para o intervalo $[4,7]$, pegaríamos a soma de $[1 ,3] = 6$ e subtrairíamos isso da soma de $[1,7] = 28$, assim sendo $28 – 6 = 22$, que é o resultado da soma de $[4,7]$. Dessa maneira, o código ficaria com uma complexidade $O(Q)$:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int v[1000000], aux[1000000]; | |
| int n,m; | |
| int main() | |
| { | |
| cin >> n >> m; //Quantidade de elementos no vetor v e a quantidade de perguntas | |
| for(int i = 1 ; i <= n ; i++) | |
| { | |
| cin >> v[i]; //O número na posição i do vetor | |
| } | |
| //igualamos as primeiras posições e percorremos da segunda até a ultima | |
| aux[1] = v[1]; | |
| for(int i = 2 ; i <= n ; ++i) | |
| { | |
| //a posição i do aux é a soma de v[1] até v[i-1] que seria o aux[i-1] + v[i] | |
| aux[i] = v[i] + aux[i-1]; | |
| } | |
| for(int i = 1 ; i <= m ; i++) | |
| { | |
| int l,r; //O intervalo [l,r] na qual queremos a soma | |
| cin >> l >> r; | |
| //e diminuimos o aux[l-1] que seia a soma de [1,l-1] do aux[r] que seria a soma de [1,r] colocando elas em uma variavel resposta | |
| int resposta; | |
| resposta = aux[r] - aux[l-1]; | |
| cout << "No intervalo de " << l << " ate " << r << " a soma e " << resposta << "\n"; | |
| } | |
| return 0; | |
| } |
Aqui vão alguns exercícios onde você pode treinar essa ideia: