955. Lazy Range Adds

Hard7.5 points estimatedSegment TreeDesignArray3 hints
RPby Rohit Parihar

A bakery tracks the number of loaves on each of several trays, numbered from 0. Build the class LazyRangeAdds from the starting counts nums.

addRange(left, right, delta) adds delta (which may be negative) to the count of every tray from left to right, both included, and returns nothing. sumRange(left, right) returns the total number of loaves on trays left to right, both included, as a 64-bit integer. Counts may become negative. Operations are applied in the given order; the expected output lists the result of each call, with null for the constructor and for every addRange.

Example 1

Input:
operations = ["LazyRangeAdds","addRange","sumRange","sumRange","addRange","sumRange"]arguments = [[[1,2,3,4,5]],[1,3,10],[0,4],[2,2],[0,4,-1],[0,1]]
Output:
[null,null,45,13,null,11]
Explanation:

After adding 10 to positions 1..3 the array is [1,12,13,14,5], whose total is 45 and whose position 2 holds 13. Adding -1 everywhere gives [0,11,12,13,4], and positions 0..1 sum to 11.

Example 2

Input:
operations = ["LazyRangeAdds","addRange","addRange","sumRange","sumRange"]arguments = [[[0,0,0]],[0,2,10000],[0,2,10000],[0,2],[1,1]]
Output:
[null,null,null,60000,20000]
Explanation:

Two additions of 10000 to every position give [20000,20000,20000]: the total is 60000 and a single position holds 20000.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -104 ≤ nums[i], delta ≤ 104
  • 0 ≤ left ≤ right < nums.length
  • At most 105 calls in total; every sum fits in a signed 64-bit integer (and stays below 253)

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.
Time per case
Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms

Expected complexity

Time
O(n) build, O(log n) per operation
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.