概要

複数の本棚について、指定された区間の本の合計冊数を高速に求める問題。

考察

この問題では、最大で \(2 \times 10^5\) 個の本棚と、同様に最大で \(2 \times 10^5\) 回の調査が行われます。もし各調査ごとに実際に区間内の本の冊数を逐一足し合わせると、最悪ケースで \(O(N \cdot Q)\) の計算が必要になり、これは \(4 \times 10^{10}\) となり、時間制限に間に合いません（通常の競技プログラミングでは \(10^8\) 程度が上限）。

そこで、事前に「累積和」というテクニックを用いることで、各調査を定数時間で処理できるようにします。累積和とは、先頭からある位置までの合計値を前もって計算しておき、任意の区間和を高速に求める方法です。

例えば、配列 \(A = [10, 20, 30, 40]\) の累積和 \(S\) は、
$\( S = [0,\ 10,\ 30,\ 60,\ 100] \)\( となり、区間 \)[2, 3]\(（1-indexed）の和は \)S[3] - S[1] = 30 - 10 = 20$ と求められます。

このように、累積和を用いることで、各クエリを \(O(1)\) で処理できます。

アルゴリズム

1. 入力を高速に読み込む（sys.stdin.read を使用）。
2. 配列 \(A\) の累積和配列 \(S\) を構築する：
   • \(S[0] = 0\)
   • \(S[i] = S[i-1] + A[i-1]\) （\(1 \leq i \leq N\)）
3. 各クエリ \([L_j, R_j]\) に対して、区間和を以下のように計算する：
   • 区間和 = \(S[R_j] - S[L_j - 1]\)
4. 結果を出力する。

計算量

• 時間計算量: \(O(N + Q)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力が非常に多いので、input() ではなく sys.stdin.read を使うことで高速化している。
• 累積和の添字に注意：配列 \(A\) は 0-indexed、累積和 \(S\) は 1-indexed で扱っている。
• クエリの範囲 \([L, R]\) は 1-indexed なので、累積和の計算時に適切に変換する必要がある。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    # 累積和配列を作成
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    # クエリ処理
    results = []
    index = 2 + N
    for _ in range(Q):
        L = int(data[index])
        R = int(data[index+1])
        index += 2
        # 区間和 [L, R] → S[R] - S[L-1]
        results.append(S[R] - S[L-1])
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。