Shelf weight queries
A warehouse aisle has a row of shelves, and the load on each shelf in kilograms is known. The safety officer asks a series of questions of the form "what is the total load on shelves a to b inclusive?" so she can compare sections of the aisle against the floor limit. There can be many questions, so recomputing the sum from scratch each time is too slow.
Read the shelf loads and the questions, then answer each question with the total load on that range.
Input
Line 1: an integer n. Line 2: n integers, the loads in kilograms, separated by spaces. Line 3: an integer q. Then q lines, each a b with 1 <= a <= b <= n (shelves are numbered from 1).
Output
q lines: the total load on shelves a to b inclusive for each question, in the order asked. If q is 0, print nothing.
Example 1
Input
5 40 15 60 5 30 3 2 4 1 5 3 3
Output
80 150 60
Shelves 2 to 4 hold 15 + 60 + 5 = 80. All five hold 150. Shelf 3 alone holds 60.
Constraints
- 1 <= n <= 3000
- 0 <= each load <= 1000000
- 0 <= q <= 1002
- 1 <= a <= b <= n
- Totals can exceed the range of a 32-bit int
Hints
Hint 1 of 3
Adding up the range for every question costs up to n operations per question. Can you do some work once, before the questions arrive, so each answer is a single subtraction?
Hint 2 of 3
Build an array prefix where prefix[i] is the sum of the first i loads, with prefix[0] = 0.
Hint 3 of 3
The total from shelf a to shelf b (1-based, inclusive) is prefix[b] - prefix[a - 1]. Use long for the prefix array: 3000 shelves of 1,000,000 kg overflow an int.
Solution
Show a reference solution and explanation
int n = int.Parse(Console.ReadLine()!);
int[] load = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();
int q = int.Parse(Console.ReadLine()!);
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + load[i];
}
for (int i = 0; i < q; i++)
{
string[] p = Console.ReadLine()!.Split(' ');
int a = int.Parse(p[0]);
int b = int.Parse(p[1]);
Console.WriteLine(prefix[b] - prefix[a - 1]);
}
Why it works
A prefix-sum array turns every range question into arithmetic. prefix[i] stores the sum of the first i loads, so the loads strictly between two positions are the difference of two prefix values. Building the array is one pass, and afterwards each of the q questions costs constant time, so the total work is proportional to n + q instead of n * q. The extra leading zero (prefix[0] = 0) is what makes the formula uniform: a range that starts at shelf 1 subtracts prefix[0] and needs no special case. Storing the sums as long matters because 3000 loads of 1,000,000 kg add up to 3,000,000,000, which does not fit in a 32-bit int; with the default unchecked arithmetic in C# an overflow would wrap around silently rather than report an error.