Soma Acumulada 1D

// SOMA ACUMULADA 1D (VETOR)
// Complexidade:
// • Criação do vetor: O(N)
// • Soma do intervalo: O(1)


#include <iostream>
using namespace std;
int main()
{
    int n;
    int s = 0;
    cin >> n;
    int vt[n], soma[n];

    //leitura da matriz
    for(int i = 0; i < n; i++)
    {
        cin >> vt[i];
        s += vt[i];
        soma[i] = s;
    }

    int a, b; //intervalo que se deseja somar
    int q; //número de intervalos
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        cin >> a >> b;
        if(a == 0)
            cout << soma[b] << endl;
        else
            cout << soma[b] - soma[a-1] << endl;
    }
    return 0;
}