概要

この問題は、\(N\) 個の要素を持つ配列に対して、指定された範囲 \([L, R]\) の合計値を求めるクエリに \(Q\) 回答える問題です。

考察

素直な方法（愚直な計算）

各クエリに対して、その都度 \(L\) 番目から \(R\) 番目までの本の冊数を足し合わせる方法が考えられます。 しかし、この方法では 1 つのクエリにつき最大で \(N\) 回の加算が必要です。最悪の場合、全体の計算量は \(O(N \times Q)\) となります。 本問題の制約では \(N, Q \le 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）に間に合いません。

効率的な方法（累積和の利用）

範囲の合計を高速に求めるために、累積和（Prefix Sum）という手法を使います。 あらかじめ「最初から \(i\) 番目までの合計」を計算しておけば、どのような範囲の合計も「引き算 1 回」で求められるようになります。

具体的には、以下のような配列 \(S\) を用意します。 - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \dots + A_i\) （\(1 \le i \le N\)）

このとき、範囲 \([L, R]\) の合計は以下の式で計算できます。 $\(\text{合計} = S[R] - S[L-1]\)\( これにより、各クエリに対して \)O(1)$ で回答することが可能になります。

アルゴリズム

1. 前処理:
   • 長さ \(N+1\) の配列 \(S\) を用意し、累積和を計算します。
   • \(S[i+1] = S[i] + A_i\) のように、前の項に現在の値を足していくことで効率的に作成できます。
2. クエリ処理:
   • 各クエリ \((L, R)\) に対して、\(S[R] - S[L-1]\) を計算して出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • 累積和の構築に \(O(N)\)、各クエリへの回答に \(O(1)\) かかるため、全体で \(O(N + Q)\) となります。
• 空間計算量: \(O(N)\)
  • 累積和を格納する配列 \(S\) のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(Q=2 \times 10^5\) のような大量の入出力を扱う場合、input() や print() を繰り返すと時間がかかることがあります。sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで、実行時間を大幅に短縮できます。

• インデックスの調整: 累積和の配列 \(S\) は、空の合計（0番目）を含めるためにサイズを \(N+1\) にします。これにより、範囲 \([L, R]\) の計算が \(S[R] - S[L-1]\) とスッキリ記述でき、境界条件の処理が楽になります。

  ソースコード

import sys

def main():
    # 全ての入力を一度に読み込み、空白文字（スペース、改行）で分割します。
    # これにより、大量の入力データを高速に処理できます。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 本棚の数 N と調査の回数 Q を取得します。
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 各本棚の本の冊数 A_1, A_2, ..., A_N を整数リストに変換します。
    # A_i は input_data のインデックス 2 から N+1 までに含まれています。
    A = list(map(int, input_data[2:N+2]))
    
    # 累積和（Prefix Sum）を計算します。
    # S[i] は 1 番目から i 番目までの本棚の本の合計冊数を表します。
    S = [0] * (N + 1)
    current_acc = 0
    for i in range(N):
        current_acc += A[i]
        S[i+1] = current_acc
    
    # 調査の範囲 [L, R] に基づいて合計冊数を求めます。
    # 調査データは input_data のインデックス N+2 以降にあります。
    results = []
    ptr = N + 2
    for _ in range(Q):
        # L_j と R_j を取得します。
        L = int(input_data[ptr])
        R = int(input_data[ptr+1])
        
        # 範囲 [L, R] の合計は、累積和を用いて S[R] - S[L-1] で求められます。
        # これは O(1) で計算可能です。
        ans = S[R] - S[L-1]
        results.append(str(ans))
        
        # 次のクエリのためにポインタを 2 進めます。
        ptr += 2
    
    # 全ての調査結果を改行区切りで一度に出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。