この問題は、列 \(T=(T _ 1,T _ 2,\ldots,T _ N)\) に対して、「区間 \(\lbrack L,R\rbrack\) が与えられるので \(T _ L+T _ {L+1}+\cdots+T _ R\) を答える」という形式のクエリを高速に処理することができれば解くことができます。

このようなクエリは、累積和と呼ばれるテクニックを用いることで高速に処理することができます。 列 \(T ^ {\text{sum}}=(T ^ {\text{sum}} _ 1,T ^ {\text{sum}} _ 2,\ldots,T ^ {\text{sum}} _ {N+1})\) を\[\begin{aligned}T ^ {\text{sum}} _ i&=T _ 1+T _ 2+\cdots+T _ {i-1}\\&=\sum _ {j=1} ^ {i-1}T _ j\end{aligned}\]として定め、値を事前に計算しておきます。 すると、質問に対して \(T _ L+T _ {L+1}+\cdots+T _ R=T ^ {\text{sum}} _ {R+1}-T ^ {\text{sum}} _ L\) として引き算を一度行うだけで答えを求めることができます。

累積和の列 \(T ^ {\text{sum}}\) を計算する際は、\(T ^ {\text{sum}} _ {i+1}=T ^ {\text{sum}} _ i+T _ i\) という関係を用いると \(O(N)\) 時間ですべての値を求めることができます。 クエリには \(O(1)\) 時間で答えることができるので、この問題を \(O(N+M)\) 時間で解くことができます。

時間計算量はオーダーレベルで悪化しますが、区間和を求めるのにセグメント木などのデータ構造を使ってもこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;

    vector<long> T(N);
    for (long& t : T) {
        cin >> t;
    }
    vector<long> partial_sum(N + 1); // 累積和の配列
    inclusive_scan(T.begin(), T.end(), partial_sum.begin() + 1); // 累積和を計算する

    for (int i = 0; i < M; ++i) {
        int S, L, R;
        cin >> S >> L >> R;
        cout << T[R] - T[L - 1] + S << endl; // 累積和を使って区間和を求めて、S を足して出力
    }
    return 0;
}

from itertools import accumulate


N, M = map(int, input().split())

T = list(map(int, input().split()))
partial_sum = [0] + list(accumulate(T)) # 累積和を計算する

for _ in range(M):
    S, L, R = map(int, input().split())
    print(partial_sum[R] - partial_sum[L - 1] + S) # 累積和を使って区間和を求めて、S を足して出力