Window overlay
HardOnline Assessment
Support range updates and range-sum queries on a row of cells.
A display has width cells numbered 0 to width - 1, all initially 0. Each command is [operation, left, right, value] and acts on the half-open range [left, right), that is cells left through right - 1:
"set": set every cell in the range tovalue."add": addvalueto every cell in the range."sum": record the sum of the cells in the range.valueis ignored.
An empty range (left == right) changes nothing and sums to 0. Process the commands in order.
Input: width, a positive integer, and commands, a list of 4-element lists.
Output: a list of the recorded sums, one per "sum" command, in order. If there are none, return [].
A direct loop over each range is fine for small inputs, but the largest inputs reward a faster data structure.
Example 1
- Input:
- [4,[["set",0,3,2],["add",1,4,1],["sum",0,4,0]]]
- Output:
- [9]
- Explanation
- Cells start [0, 0, 0, 0]. Set [0, 3) to 2 gives [2, 2, 2, 0]; add 1 to [1, 4) gives [2, 3, 3, 1]. The sum of all four cells is 9.
Example 2
- Input:
- [5,[["set",0,5,1],["add",1,3,4],["sum",0,2,0],["sum",2,5,0],["set",2,4,0],["sum",0,5,0]]]
- Output:
- [6,7,7]
- Explanation
- After the set the cells are [1, 1, 1, 1, 1]; adding 4 to [1, 3) gives [1, 5, 5, 1, 1]. Sum of [0, 2) is 6 and of [2, 5) is 7. Setting [2, 4) to 0 gives [1, 5, 0, 0, 1], whose total is 7.
Example 3
- Input:
- [2,[["add",0,2,-3],["sum",1,1,0],["sum",0,2,0]]]
- Output:
- [0,-6]
- Explanation
- Adding -3 to both cells gives [-3, -3]. The range [1, 1) is empty, so its sum is 0. The whole range sums to -6.
Constraints
1 <= width <= 20,0000 <= commands.length <= 2,0000 <= left <= right <= width-1,000 <= value <= 1,000