概要

連続する本棚の範囲に含まれる本の合計冊数を求める問題です。累積和を用いることで、各クエリに \(O(1)\) で答えることができます。

考察

素朴なアプローチとその問題点

各クエリに対して、範囲 \([L, R]\) の本の冊数を愚直に足し合わせる方法を考えます。

for i in range(L, R+1):
    answer += A[i]

この方法では、1回のクエリあたり最悪 \(O(N)\) の時間がかかります。クエリが \(Q\) 回あるので、全体で \(O(NQ)\) となります。

\(N, Q\) がともに最大 \(2 \times 10^5\) なので、\(NQ\) は最大 \(4 \times 10^{10}\) 回の計算が必要になり、TLE（時間制限超過） になってしまいます。

重要な気づき：累積和の活用

「区間の合計」を高速に求めるには、累積和（Prefix Sum） が有効です。

累積和配列 \(S\) を以下のように定義します： - \(S[0] = 0\) - \(S[i] = A[1] + A[2] + \cdots + A[i]\)（\(i \geq 1\)）

すると、区間 \([L, R]\) の合計は次の式で \(O(1)\) で計算できます： $\(\sum_{i=L}^{R} A[i] = S[R] - S[L-1]\)$

具体例

\(A = [3, 1, 4, 1, 5]\) の場合：

インデックス	0	1	2	3	4	5
\(S\)	0	3	4	8	9	14

• 区間 \([2, 4]\) の合計 = \(S[4] - S[1] = 9 - 3 = 6\)（\(A[2] + A[3] + A[4] = 1 + 4 + 1 = 6\)）
• 区間 \([1, 5]\) の合計 = \(S[5] - S[0] = 14 - 0 = 14\)

アルゴリズム

1. 前処理: 累積和配列 \(S\) を構築する

   • \(S[0] = 0\) で初期化
   • \(i = 1, 2, \ldots, N\) に対して \(S[i] = S[i-1] + A[i]\) を計算

2. クエリ処理: 各クエリ \((L, R)\) に対して

   • 答えを \(S[R] - S[L-1]\) で計算して出力

計算量

• 時間計算量: \(O(N + Q)\)
  • 累積和の構築に \(O(N)\)
  • 各クエリの処理に \(O(1)\)、全体で \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 累積和配列を保持するため

実装のポイント

1. インデックスのずれに注意: 問題文では本棚は1-indexedですが、Pythonの配列は0-indexedです。累積和配列を長さ \(N+1\) で作り、\(S[0] = 0\) とすることで、\(S[R] - S[L-1]\) の計算がシンプルになります。

2. オーバーフロー対策: \(A_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、合計は最大 \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローは起きませんが、C++などでは long long を使う必要があります。

3. 高速な入出力: \(Q\) が大きいため、結果を一度リストに溜めてから一括出力することで、出力処理を高速化しています。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 累積和を計算
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + A[i]
    
    # 各クエリに対して答えを出力
    results = []
    for _ in range(Q):
        L, R = map(int, input().split())
        results.append(prefix_sum[R] - prefix_sum[L - 1])
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。