Informática Ideia 06 - Soma de Prefixos

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;
	}

view raw

ideia_06_01.cpp

hosted with ❤ by GitHub

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;
	}

view raw

ideia_06_02.cpp

hosted with ❤ by GitHub

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