Skills101
← All coding problems

Range Sum Queries

easyArrays & Prefix Sums+10 XPTime limit 2s

A shop keeps its sales of each day in an array. The manager asks many questions of the form "what were the total sales from day l to day r?". Answer every question.

Input:

  • line 1: n
  • line 2: n integers (sales can be negative — refunds)
  • line 3: q
  • next q lines: l r (1-based, l ≤ r)

Output: q lines — the sum of a[l..r] for each query.

Constraints: 1 ≤ n, q ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹ (sums need 64-bit integers).

Think about it: adding up the range for every query is O(n·q). Build a prefix sum array once: p[i] = sum of the first i elements. Then any range sum is p[r] − p[l − 1], in O(1).

Sample input 1

5
3 -1 4 1 5
3
1 3
2 5
4 4

Sample output 1

6
9
1

Sample input 2

1
7
2
1 1
1 1

Sample output 2

7
7

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.