概要

連続区間 \([L, R]\) の本の合計を \(Q\) 回求める問題です。累積和を作って各クエリを \(O(1)\) で答えます。

考察

各調査で「\(L\) 番目から \(R\) 番目までの合計」を求めたいので、素朴に毎回 \(A_L + A_{L+1} + \cdots + A_R\) を足すとします。
しかし最悪の場合、1 回の調査が長さ \(N\) になり得て、それが \(Q\) 回あるので計算量は \(O(NQ)\) になります。制約は \(N, Q \le 2 \times 10^5\) なので、\(O(NQ)\) は到底間に合いません。

ここで重要な気づきは、区間和は累積和（prefix sum）を使うと引き算 1 回で出せることです。

例えば、累積和を - \(pref[0] = 0\) - \(pref[i] = A_1 + A_2 + \cdots + A_i\)

と定義すると、区間 \([L, R]\) の和は

\[ A_L + \cdots + A_R = pref[R] - pref[L-1] \]

となります。
例：\(A = [3, 1, 4, 1, 5]\) のとき
\(pref = [0, 3, 4, 8, 9, 14]\)
区間 \([2, 4]\) の和は \(pref[4]-pref[1] = 9-3 = 6\)（実際に \(1+4+1=6\)）です。

これにより、各クエリを高速に処理できます。

アルゴリズム

1. 配列 \(A\) から累積和配列 \(pref\)（長さ \(N+1\)）を作る。
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+A_i\)（\(i=1..N\)）
2. 各クエリ \((L, R)\) について、答えを \(pref[R] - pref[L-1]\) として出力する。

計算量

• 時間計算量: \(O(N + Q)\)（累積和の構築に \(O(N)\)、各クエリに \(O(1)\) で合計 \(O(Q)\)）
• 空間計算量: \(O(N)\)（累積和配列）

実装のポイント

• 1-indexed の累積和にすると式が \(pref[R]-pref[L-1]\) で統一でき、境界処理が簡単です（\(pref[0]=0\) が効く）。

• 出力が多いので、print を毎回呼ぶよりも、答えを配列に溜めて最後にまとめて出力すると高速です。

• \(A_i\) は最大 \(10^9\)、\(N\) は最大 \(2\times 10^5\) なので合計は最大で \(2\times 10^{14}\) 程度になり得ます。Python の int なら問題ありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    pref = [0] * (N + 1)
    s = 0
    for i, x in enumerate(A, 1):
        s += x
        pref[i] = s

    out = []
    for _ in range(Q):
        L, R = map(int, input().split())
        out.append(str(pref[R] - pref[L - 1]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。