Overview

This is a problem of finding the total number of books contained in a contiguous range of bookshelves. By using prefix sums, we can answer each query in \(O(1)\) time.

Analysis

Naive Approach and Its Problems

Consider a method that naively sums up the number of books in the range \([L, R]\) for each query.

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

This method takes \(O(N)\) time in the worst case per query. Since there are \(Q\) queries, the total time complexity becomes \(O(NQ)\).

Since both \(N\) and \(Q\) can be up to \(2 \times 10^5\), \(NQ\) would require up to \(4 \times 10^{10}\) calculations, resulting in TLE (Time Limit Exceeded).

Key Insight: Using Prefix Sums

To efficiently compute “range sums”, Prefix Sum is effective.

Define the prefix sum array \(S\) as follows: - \(S[0] = 0\) - \(S[i] = A[1] + A[2] + \cdots + A[i]\) (for \(i \geq 1\))

Then, the sum of the range \([L, R]\) can be computed in \(O(1)\) using the following formula: $\(\sum_{i=L}^{R} A[i] = S[R] - S[L-1]\)$

Concrete Example

For \(A = [3, 1, 4, 1, 5]\):

Index	0	1	2	3	4	5
\(S\)	0	3	4	8	9	14

• Sum of range \([2, 4]\) = \(S[4] - S[1] = 9 - 3 = 6\) (\(A[2] + A[3] + A[4] = 1 + 4 + 1 = 6\))
• Sum of range \([1, 5]\) = \(S[5] - S[0] = 14 - 0 = 14\)

Algorithm

1. Preprocessing: Build the prefix sum array \(S\)

   • Initialize with \(S[0] = 0\)
   • For \(i = 1, 2, \ldots, N\), compute \(S[i] = S[i-1] + A[i]\)

2. Query Processing: For each query \((L, R)\)

   • Compute and output the answer as \(S[R] - S[L-1]\)

Complexity

• Time Complexity: \(O(N + Q)\)
  • \(O(N)\) for building the prefix sum
  • \(O(1)\) for each query, \(O(Q)\) in total
• Space Complexity: \(O(N)\)
  • For storing the prefix sum array

Implementation Notes

1. Be careful with index offsets: In the problem statement, bookshelves are 1-indexed, but Python arrays are 0-indexed. By creating the prefix sum array with length \(N+1\) and setting \(S[0] = 0\), the calculation of \(S[R] - S[L-1]\) becomes simple.

2. Overflow prevention: Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the sum can reach approximately \(2 \times 10^{14}\). In Python, integer overflow does not occur, but in C++ and similar languages, you need to use long long.

3. Fast I/O: Since \(Q\) can be large, we speed up the output process by collecting results in a list first and then printing them all at once.

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Compute prefix sum
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + A[i]
    
    # Output the answer for each query
    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()

---

This editorial was generated by claude4.5opus.