Overview

A problem where, given multiple bookshelves, we need to quickly compute the total number of books in a specified range.

Analysis

In this problem, there are up to \(2 \times 10^5\) bookshelves and up to \(2 \times 10^5\) queries. If we naively sum up the number of books in the range for each query, the worst case requires \(O(N \cdot Q)\) operations, which amounts to \(4 \times 10^{10}\) — far too slow to meet the time limit (in typical competitive programming, around \(10^8\) operations is the upper limit).

To address this, we use a technique called “prefix sums” to preprocess the data so that each query can be answered in constant time. A prefix sum precomputes the cumulative total from the beginning up to each position, allowing us to quickly compute the sum of any range.

For example, given the array \(A = [10, 20, 30, 40]\), the prefix sum array \(S\) is: $\( S = [0,\ 10,\ 30,\ 60,\ 100] \)\( The sum of the range \)[2, 3]\( (1-indexed) can be computed as \)S[3] - S[1] = 30 - 10 = 20$.

In this way, by using prefix sums, each query can be processed in \(O(1)\).

Algorithm

1. Read input efficiently (using sys.stdin.read).
2. Build the prefix sum array \(S\) from array \(A\):
   • \(S[0] = 0\)
   • \(S[i] = S[i-1] + A[i-1]\) (\(1 \leq i \leq N\))
3. For each query \([L_j, R_j]\), compute the range sum as follows:
   • Range sum = \(S[R_j] - S[L_j - 1]\)
4. Output the results.

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the input is very large, we use sys.stdin.read instead of input() for faster reading.

• Pay attention to prefix sum indexing: array \(A\) is 0-indexed, while the prefix sum array \(S\) is treated as 1-indexed.

• The query ranges \([L, R]\) are 1-indexed, so appropriate conversion is needed when computing with the prefix sum array.

  Source Code

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

This editorial was generated by qwen3-coder-480b.