Range Sum Query (RSQ)
Este problema consiste em calcular a soma dos valores de um dado intervalo de um conjunto de números.
Por exemplo, se o conjunto dado for:
1 5 6 8 8 0 4 -4
rsq(1,3) = 19, pois queremos a soma dos elementos entre os índices 1 e 3: 5 + 6 + 8
rsq(0,2) = 12
rsq(3,6) = 20
e assim por diante.
Seja n o número de elementos do array;
Sejam i e j os dois índices do intervalo ( 0 <= i <= j < n);
Seja sum um array global: int sum[n];
Seja array um array global: int array[n];
Caso você deseje fazer apenas uma consulta, então esse problema é resolvido fazendo simplesmente um loop de i a j e somando os valores:
int rsq(int i, int j){ int sum = 0; for (int k=i; k <=j; ++k) { sum += array[k]; } return sum;}Perceba que essa função é O(n). Logo, se forem feitas m consultas, teremos O(mn). Para m pequeno, essa pode ser uma solução aceitável. Porém, para m grande, podemos construir uma solução de maneira bem fácil em O(1), bastando fazer um pré-processamento em O(n). Além disso, o pré-processamento pode ser feito na leitura dos dados, o que teria que ser feito de qualquer maneira.
A ideia é criar um outro array para acumular a soma dos elementos. Quando quisermos saber a soma de um intervalo, basta subtrair os dois valores da soma acumulada:
/**Rodrigo Paes*/#include <bits/stdc++.h>using namespace std;#define MAX_N 1000#define FILL_0(a) memset(a, 0, sizeof a)int sum[MAX_N];int array[MAX_N];/*Range sum query[i, j]O(1)*/int rsq(int i, int j){ int start = i >0 ? sum[i-1] : 0; return sum[j]-start;}int main(){ int n, q, s, e; cin >> n; FILL_0(array); FILL_0(sum); for (int i=0; i<n; ++i) { cin >> array[i]; // pré-processamento: constrói o array de soma, acumulada. sum[i] = i>0? sum[i-1] + array[i] : array[i]; } cin >> q; while (q--) { cin >> s >> e; cout << rsq(s,e) << endl; }}RSQ com atualização dos valores.
Suponha que os valores do array possam ser alterados entre uma query e outra. Nesse caso, para cada alteração do array, teríamos que atualizar o array sum da posição da alteração até o final do array. Ou seja, uma operação em O(n).
Duas formas de resolver esse problema são com Segment trees e com Fenwick trees. Em ambas, a consulta e a atualização de valores são feitas em O(log(n)) e a sua construção é feita em O(n).
Originalmente a Fenwick tree é utilizada para o cálculo da soma de um prefixo, Ou seja, qual o valor da soma acumulado até um determinado índice. Entretanto, ela pode ser adaptada para retornar a soma de um intervalo bastando chamar a fenwick duas vezes, uma com o índice do ínicio do intervalo e outra com o fim do intervalo, e depois subtraíndo esses valores.
Portanto, essas opções só valem a pena se forem feitas muitas modificações e/ou muitas consultas.