#210HardRange Queries· Segment Tree with Lazy Range Add and Range Max

Server Load Tracker

A cloud provider models a row of `size` server slots numbered `0` to `size - 1`. Every slot starts with a load of 0. Jobs add load to a whole range of neighbouring slots at once, and finish by removing it again, while the dashboard repeatedly asks for the **peak load** inside a range of slots. Design a class `ServerLoadTracker`: - `ServerLoadTracker(size)` creates the tracker with all loads at 0. - `addLoad(left, right, amount)` adds `amount` (which may be negative) to every slot from `left` to `right`, both inclusive. - `peakLoad(left, right)` returns the largest current load among the slots from `left` to `right`, both inclusive. Looping over the slots for every call is too slow when ranges are long and calls are frequent.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: null for the constructor and for `addLoad`, and the peak load for each `peakLoad`.

Examples

Input: operations = ["ServerLoadTracker", "addLoad", "addLoad", "peakLoad", "peakLoad", "addLoad", "peakLoad"], arguments = [[6], [1, 3, 5], [2, 5, 4], [0, 5], [4, 5], [2, 2, -6], [0, 5]]

Output: [null, null, null, 9, 4, null, 9]

After the two adds the loads are 0, 5, 9, 9, 4, 4. The peak over all slots is 9 and over slots 4 to 5 is 4. Removing 6 from slot 2 leaves 0, 5, 3, 9, 4, 4, whose peak is 9.

Input: operations = ["ServerLoadTracker", "peakLoad", "addLoad", "peakLoad", "addLoad", "peakLoad"], arguments = [[3], [0, 2], [0, 2, -2], [0, 2], [1, 1, 7], [0, 1]]

Output: [null, 0, null, -2, null, 5]

Initially every load is 0. Subtracting 2 everywhere makes the peak -2. Adding 7 to slot 1 makes slot 1 equal 5, which is the peak of slots 0 and 1.

Constraints

1 <= size <= 10^5
0 <= left <= right < size
-1000 <= amount <= 1000
At most 10^4 calls in total

#segment-tree
#lazy-propagation
#range-update
#range-maximum
#design