Overview

A problem where, given multiple range sum queries, we need to efficiently determine whether the sum of each range exceeds a budget limit.

Analysis

In this problem, we need to repeatedly compute the sum of different ranges over the same array.
For example, the sum of the range \([L, R]\) is \(A_L + A_{L+1} + \cdots + A_R\), but computing this naively each time takes \(O(N)\) in the worst case, resulting in an overall time complexity of \(O(QN)\). Given the constraints \(N, Q \leq 2 \times 10^5\), this is too slow (requiring up to \(4 \times 10^{10}\) operations).

Therefore, we use prefix sums as a method to “compute range sums efficiently.”
A prefix sum is a data structure that precomputes and stores the sum from the beginning of the array up to each position.
Specifically, we define an array \(S\) as follows: - \(S[0] = 0\) - \(S[i] = A[0] + A[1] + \cdots + A[i-1]\) (in 0-indexed terms)

With this, the sum of any range \([L, R]\) can be computed in \(O(1)\) as \(S[R+1] - S[L]\) (or \(S[R] - S[L-1]\) in 1-indexed terms).

Using this technique, the precomputation takes \(O(N)\) and each query takes \(O(1)\), giving an overall time complexity of \(O(N + Q)\).

Algorithm

1. Read the input (using sys.stdin.read for speed).
2. Build the prefix sum array \(S\) from array \(A\):
   • \(S[0] = 0\)
   • \(S[i] = S[i-1] + A[i-1]\)
3. For each query \([L_j, R_j]\), compute the range sum as \(S[R_j] - S[L_j - 1]\).
4. If the range sum exceeds \(T\), output Yes; otherwise, output No.

Example

Sample input:

5 3 10
1 2 3 4 5
1 3
2 5
1 5

• Prefix sum array \(S\): [0, 1, 3, 6, 10, 15]
• Query 1 (range 1 to 3): \(S[3] - S[0] = 6 - 0 = 6\) → No
• Query 2 (range 2 to 5): \(S[5] - S[1] = 15 - 1 = 14\) → Yes
• Query 3 (range 1 to 5): \(S[5] - S[0] = 15 - 0 = 15\) → Yes

Output:

No
Yes
Yes

Complexity

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

Implementation Notes

• Since the input can be very large, use sys.stdin.read for fast reading.

• Be careful with prefix sum indexing (whether it’s 1-indexed or 0-indexed).

• The range sum is computed as \(S[R] - S[L-1]\) (1-indexed) or \(S[R+1] - S[L]\) (0-indexed).

• Collecting all results and outputting them together at the end is even faster.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    T = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    
    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    idx = 3 + N
    results = []
    for _ in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        total = S[R] - S[L-1]
        if total > T:
            results.append("Yes")
        else:
            results.append("No")
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

---

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