Overview

Given an array of product prices at a store, the problem asks to determine whether the total value of each interval exceeds a budget limit \(T\) for multiple range queries.

Analysis

In this problem, we need to efficiently compute the total value of each interval \([L_j, R_j]\) for up to 200,000 queries. A naive approach of directly traversing the array to compute the total for each query would take \(O(N)\) time per query, resulting in \(O(NQ)\) total operations—up to \(4 \times 10^{10}\) computations—which cannot be processed within the time limit.

The key to solving this problem efficiently is to precompute a prefix sum array, which allows each query to be processed in constant time \(O(1)\).

Algorithm

We use a technique called Prefix Sum. The specific steps are as follows:

1. Building the prefix sum array:

   • Create an array prefix_sum of length \(N+1\)
   • Initialize prefix_sum[0] = 0
   • For \(i = 1\) to \(N\), compute prefix_sum[i] = prefix_sum[i-1] + A[i-1]
   • As a result, prefix_sum[i] represents the sum of the first \(i\) elements

2. Query processing:

   • The total value of the interval \([L, R]\) can be computed as prefix_sum[R] - prefix_sum[L-1]
   • Determine whether this total value is greater than \(T\)

For example, if \(A = [3, 1, 4, 1, 5]\), \(L=2\), \(R=4\): - prefix_sum[4] = 3+1+4+1 = 9 - prefix_sum[1] = 3 - Total = \(9 - 3 = 7\) (\(A_2 + A_3 + A_4 = 1+4+1\))

Complexity

• Time complexity: \(O(N + Q)\)
  • \(O(N)\) to build the prefix sum array
  • \(O(1)\) per query, \(O(Q)\) for \(Q\) queries
• Space complexity: \(O(N)\)
  • \(O(N)\) memory to store the prefix sum array

Implementation Notes

• The size of the prefix sum array should be 1 larger than the original array, i.e., \((N+1)\)

• Be careful with indexing: the \(i\)-th element of the original array corresponds to A[i-1]

• The total value of the query interval \([L, R]\) can be computed as prefix_sum[R] - prefix_sum[L-1]

• Since we handle large numbers (\(T\) can be up to \(10^{14}\)), be cautious of integer overflow (in Python, this is not an issue since arbitrary-precision integers are used automatically)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    q = int(data[1])
    T = int(data[2])
    A = list(map(int, data[3:3+n]))
    queries = []
    index = 3 + n
    for i in range(q):
        L = int(data[index])
        R = int(data[index+1])
        queries.append((L, R))
        index += 2
        
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i-1] + A[i-1]
        
    results = []
    for (L, R) in queries:
        total = prefix_sum[R] - prefix_sum[L-1]
        if total > T:
            results.append("Yes")
        else:
            results.append("No")
            
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.