RSQ y Sumas Cumulativas

Consideremos el siguiente problema: tenemos una sequencia $a_1, a_2, \ldots, a_n$ de números y se nos pide calcula la suma de los términos $a_L, a_{L+1}, \ldots, a_R$, para varios pares $(L, R)$, es decir:

\[ \sum_{i=L}^R a_i \]

(Este problema se conoce como Range Sum Query, RSQ)

¿Cómo resolver este problema? La primera forma que se nos puede ocurrir es iterar desde $L$ a $R$ e ir sumando. Es $\mathcal{O}(n)$ por cada consulta a un rango $(L, R)$. Si nos piden muchas consultas, hay una idea que nos permite hacerlo de forma más eficiente. Definimos $s_i$ como la suma de los $i$ primeros elementos: $s_i=\sum_{j=1}^i a_j, s_0=0$. En código, calculamos esta secuencia de la siguiente forma:

vector<int> s (n+1); //si a tiene tamaño n, s tiene tamaño n+1
s[0] = 0;
for(int i=0; i < n; ++i) {    
    s[i+1] = s[i] + a[i]; //a indizada empezando por 0.
}

(Hemos usado que $s_{i+1}=s_i+a_{i+1}$ (en el código a[i] en lugar de a[i+1] porque empezamos en a[0]), ya que la suma de los $i+1$ primeros elementos es la suma de los $i$ primeros más el \((i+1)\)-ésimo).

La clave está en que ahora la respuesta al problema es simplemente $s_R-s_{L-1}$(ojo: si el vector empieza con índice 0, como en el código que hemos puesto, es s[R+1]-s[L]). Esto es porque la suma desde el $L$-ésimo elemento hasta el $R$-ésimo  elemento se obtiene restando de la suma desde el principio hasta el $R$-ésimo elemento los $L-1$ primeros términos. Así, una vez hemos calculado el vector s, podemos responder cualquier consulta en tiempo \( O(1) \).

Esta idea (conocida como sumas cumulativas, sumas parciales, sumas del prefijo, prefix sums, partial sums) de ir considerando los valores de los prefijos cumulativamente no sólo se usa para resolver el problema de RSQ, sino que puede aparecer en otros contextos, tal vez de forma más abstracta.

Una variante del problema de RSQ es el RSQ dinámico: es igual que el RSQ, pero además de realizar consultas se pueden realizar “actualizaciones” de la secuencia a. Este problema no se puede resolver con sumas cumulativas directamente, porque no se pueden actualizar eficientemente todos los valores del vector s necesarios. Para ello son necesarias estructuras de datos más complejas, como el Árbol de segmentos.