Solução Informática Iniciante - Semana 55 - Problema 1

Para esse problema usaremos a ideia de soma de prefixos, ou soma acumulada, do vetor $v$ . A ideia é, guardamos um vetor $pref[N]$ , onde $pref[i]$ significa a soma de todas as posições de $v$ de $1$ até $i$ . Por exemplo, se $v = {1, 2, 3, 4, 5}$ então $pref[3] = 1 + 2 + 3$ . Note que a soma do intervalo $[a, b]$ pode ser escrita como $pref[b] - pref[a - 1]$ .

Portanto, basta calcularmos a soma de prefixos para o vetor dado e para cada pergunta apenas consultamos o vetor de prefixos. Então para cada pergunta imprimimos a soma total do vetor menos a soma do intervalo $[a, b]$ .

Complexidade: $\mathcal{O} (Q)$

	#include <bits/stdc++.h>
	using namespace std;
	const int maxn = 5e5 + 10;

	int n, q, pref[maxn], v[maxn];

	int main()
	{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n >> q;

	for(int i = 1; i <= n; i++)
	cin >> v[i];

	for(int i = 1; i <= n; i++)
	pref[i] = pref[i - 1] + v[i];

	int total = pref[n]; // soma de todos

	for(int i = 0; i < q; i++)
	{
	int a, b;
	cin >> a >> b;

	cout << total - (pref[b] - pref[a - 1]) << "\n";
	}
	}

view raw

inis55p1.cpp

hosted with ❤ by GitHub