累積和を用いてこの問題に正解できます。

まず、予め \(S_k=A_1+A_2+\dots+A_k\) を計算しておきます。これは時間計算量 \(O(N)\) で実現できます。

その後、クエリ \((L_i,R_i)\) について \(S_{R_i}-S_{L_i-1}\) の値が \(A_{L_i}+A_{L_i+1}+\dots+A_{R_i}\) となります。
このことは \(S\) の定義から計算すると分かります。クエリ当たり時間計算量 \(O(1)\) で計算可能です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,Q;
  cin >> N >> Q;
  vector<ll> A(N+1,0);
  for(ll i=1;i<=N;i++){
    cin >> A[i];
    A[i]+=A[i-1];
  }
  while(Q--){
    ll L,R;
    cin >> L >> R;
    cout << A[R]-A[L-1] << "\n";
  }
  return 0;
}