77. Quick Range Totals

EasyArrayPrefix SumDesign
RPby Rohit Parihar

A weather station stores its hourly rainfall readings in an array and answers a long stream of questions of the form "how much rain fell between hour left and hour right?". Recomputing each total from scratch would be wasteful, so the station wants a small helper class.

Implement the class RangeTotals. The constructor RangeTotals(nums) receives the integer array nums once. The method sumRange(left, right) returns the sum of the elements of nums from index left to index right, both inclusive. The constructor returns nothing. The array is never modified between calls.

Example 1

Input:
operations = ["RangeTotals","sumRange","sumRange","sumRange"]arguments = [[[4,-2,7,1,5]],[0,2],[1,3],[4,4]]
Output:
[null,9,6,5]
Explanation:

The queries sum 4-2+7=9, then -2+7+1=6, then the single element 5.

Example 2

Input:
operations = ["RangeTotals","sumRange","sumRange"]arguments = [[[10,20,30]],[0,2],[1,1]]
Output:
[null,60,20]
Explanation:

The whole array sums to 60 and the single element at index 1 is 20.

Constraints

1 ≤ nums.length ≤ 104

-1000 ≤ nums[i] ≤ 1000

0 ≤ left ≤ right < nums.length

At most 104 calls to sumRange

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(n) build, O(1) per query
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.