Overview

This problem requires answering \(Q\) queries, each asking for the sum of elements in a specified range \([L, R]\) of an array with \(N\) elements.

Analysis

Straightforward Approach (Brute Force)

For each query, one could simply add up the values from the \(L\)-th to the \(R\)-th element. However, this method requires up to \(N\) additions per query. In the worst case, the total computation is \(O(N \times Q)\). Given the constraints of this problem where \(N, Q \le 2 \times 10^5\), this would require up to approximately \(4 \times 10^{10}\) operations, which will not fit within the time limit (typically around 2 seconds).

Efficient Approach (Using Prefix Sums)

To quickly compute range sums, we use a technique called Prefix Sum. By precomputing “the sum from the first element up to the \(i\)-th element,” any range sum can be obtained with “a single subtraction.”

Specifically, we prepare an array \(S\) as follows: - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \dots + A_i\) (\(1 \le i \le N\))

Then, the sum of the range \([L, R]\) can be computed with the following formula: $\(\text{Sum} = S[R] - S[L-1]\)\( This allows us to answer each query in \)O(1)$.

Algorithm

1. Preprocessing:
   • Prepare an array \(S\) of length \(N+1\) and compute the prefix sums.
   • This can be efficiently constructed by adding the current value to the previous term: \(S[i+1] = S[i] + A_i\).
2. Query Processing:
   • For each query \((L, R)\), compute and output \(S[R] - S[L-1]\).

Complexity

• Time Complexity: \(O(N + Q)\)
  • Building the prefix sum takes \(O(N)\), and answering each query takes \(O(1)\), so the overall complexity is \(O(N + Q)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array \(S\) that stores the prefix sums.

Implementation Notes

• Fast I/O: When handling a large amount of input/output such as \(Q=2 \times 10^5\) in Python, repeatedly calling input() and print() can be slow. By reading all input at once with sys.stdin.read().split() and writing all output at once with sys.stdout.write(), the execution time can be significantly reduced.

• Index Adjustment: The prefix sum array \(S\) is sized \(N+1\) to include the empty sum (index 0). This allows the range \([L, R]\) calculation to be neatly written as \(S[R] - S[L-1]\), making boundary condition handling easier.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.