951. Live Range Totals

Medium3.5 points estimatedBinary Indexed TreeDesignArray3 hints
RPby Rohit Parihar

A greenhouse monitors a row of sensors numbered from 0, and each sensor holds one integer temperature offset. Implement the class LiveRangeTotals, which is built from the initial readings nums.

update(index, val) overwrites the reading of sensor index with val (it does not add) and returns nothing. sumRange(left, right) returns the sum of the readings of sensors left to right, both ends included. The operations of a test are applied in the given order, and the expected output lists what each operation returned, with null for update and for the constructor call.

Example 1

Input:
operations = ["LiveRangeTotals","sumRange","update","sumRange","sumRange"]arguments = [[[4,-2,7,1,5]],[0,4],[1,6],[1,3],[0,0]]
Output:
[null,15,null,14,4]
Explanation:

The whole row sums to 4-2+7+1+5 = 15. After update(1, 6) the row is [4,6,7,1,5], so positions 1..3 give 6+7+1 = 14, and position 0 alone is 4. update returns null.

Example 2

Input:
operations = ["LiveRangeTotals","sumRange","update","sumRange","update","sumRange"]arguments = [[[10,20,30]],[1,2],[2,-5],[1,2],[0,0],[0,2]]
Output:
[null,50,null,15,null,15]
Explanation:

20+30 = 50 at first; after setting position 2 to -5 the same range gives 20-5 = 15; after setting position 0 to 0 the full row [0,20,-5] sums to 15.

Constraints

  • 1 ≤ nums.length ≤ 105
  • -104 ≤ nums[i], val ≤ 104
  • 0 ≤ index < nums.length and 0 ≤ left ≤ right < nums.length
  • At most 105 calls in total, so every range sum always fits in a 32-bit integer

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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 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.