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)$$
https://gist.github.com/lawrencefmm/fed09f9963e4a287d2ebbd4177667798
Deixe um comentário