Overview

This is a problem where we need to compute the sum of books in a contiguous interval \([L, R]\) for \(Q\) queries. We build a prefix sum array and answer each query in \(O(1)\).

Analysis

For each query, we want to find “the sum from the \(L\)-th to the \(R\)-th element,” so a naive approach would be to compute \(A_L + A_{L+1} + \cdots + A_R\) each time.
However, in the worst case, a single query can span a length of \(N\), and with \(Q\) such queries, the total time complexity becomes \(O(NQ)\). Given the constraints \(N, Q \le 2 \times 10^5\), \(O(NQ)\) is far too slow.

The key insight here is that interval sums can be computed with a single subtraction using a prefix sum.

For example, if we define the prefix sum as: - \(pref[0] = 0\) - \(pref[i] = A_1 + A_2 + \cdots + A_i\)

then the sum of the interval \([L, R]\) is:

\[ A_L + \cdots + A_R = pref[R] - pref[L-1] \]

Example: When \(A = [3, 1, 4, 1, 5]\),
\(pref = [0, 3, 4, 8, 9, 14]\)
The sum of the interval \([2, 4]\) is \(pref[4]-pref[1] = 9-3 = 6\) (indeed \(1+4+1=6\)).

This allows us to process each query efficiently.

Algorithm

1. Build a prefix sum array \(pref\) (of length \(N+1\)) from the array \(A\).
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+A_i\) (\(i=1..N\))
2. For each query \((L, R)\), output the answer as \(pref[R] - pref[L-1]\).

Complexity

• Time complexity: \(O(N + Q)\) (building the prefix sum takes \(O(N)\), and each query takes \(O(1)\) for a total of \(O(Q)\))
• Space complexity: \(O(N)\) (for the prefix sum array)

Implementation Notes

• Using a 1-indexed prefix sum unifies the formula as \(pref[R]-pref[L-1]\) and simplifies boundary handling (since \(pref[0]=0\) serves as the base case).

• Since there are many outputs, it is faster to accumulate the answers in an array and print them all at once at the end, rather than calling print each time.

• \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2\times 10^5\), so the total sum can reach approximately \(2\times 10^{14}\). Python’s int handles this without any issues.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    pref = [0] * (N + 1)
    s = 0
    for i, x in enumerate(A, 1):
        s += x
        pref[i] = s

    out = []
    for _ in range(Q):
        L, R = map(int, input().split())
        out.append(str(pref[R] - pref[L - 1]))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.