How much rain fell
You are given a series of daily rainfall over n days. A meteorologist needs to answer q questions of the form “how much fell from day l to day r inclusive”. There are many questions, and the periods can be long: tens of years.
The second and third tests are Almaty’s daily rainfall for 1941–2025 (the ERA5 reanalysis via Open-Meteo), in tenths of a millimetre.
Input
The first line holds n (1 ≤ n ≤ 2·10⁵), the second n integers from 0 to 10⁶. Then q (1 ≤ q ≤ 10⁵) and q lines with the numbers l and r (1 ≤ l ≤ r ≤ n).
Output
For each question, the sum of the numbers from the l-th to the r-th.
Examples
Example 1
8 0 12 0 35 7 0 0 120 5 1 8 2 2 4 5 6 7 1 1
174 12 42 0 0
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If each question adds up its days anew, then with 10⁵ questions over 2·10⁵ days that is 2·10¹⁰ additions. What can be computed once in advance so as to answer quickly afterwards?
2The idea
Compute P[i], the sum of the first i days, with P[0] = 0. Then the sum from day l to day r is P[r] − P[l − 1]: from the sum of the first r days subtract everything before day l.
3Walkthrough
One pass builds P, and each question is one subtraction. It is convenient that the array is one longer than the original: then the formula works for l = 1 too, without a special case.
The sums are large: 2·10⁵ days of 10⁶ each make 2·10¹¹, which does not fit in a 32-bit integer. In Go we use int64.
3+Solution
4Complexity
O(n) to build and O(1) per question, O(n + q) in all. Memory O(n).
5Common mistakes
- Adding up each period anew. Correct, but the third test is 10⁵ questions about periods of seventy to eighty years, almost 3·10⁹ additions.
- Off by one. Days in the statement are numbered from one, and P[i] is the sum of the first i. Check the question “2 2” on the first example.
- Overflow. In the fifth test the sum is 5·10¹⁰.