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)