1248. Span Adjuster
Design a class SpanAdjuster that manages an array of n integers, all 0 at the start; the constructor receives n. add(left, right, delta) adds delta to every position from left to right, both included, and returns nothing. valueAt(index) returns the current value at position index as a long. total() returns the sum of all n values as a long.
Positions are 0-based and delta may be negative. Store the differences between neighbouring positions in a Fenwick tree so every call runs in O(log n) time, with O(n) space overall.
Example 1
- Input:
- operations = ["SpanAdjuster","add","valueAt","total","add","valueAt","valueAt","valueAt","total"]arguments = [[5],[0,4,1],[2],[],[1,3,2],[0],[1],[4],[]]
- Output:
- [null,null,1,5,null,1,3,1,11]
- Explanation:
After adding 1 everywhere and then 2 to positions 1 to 3, the values are 1, 3, 3, 3, 1, so the total is 11.
Example 2
- Input:
- operations = ["SpanAdjuster","add","valueAt","total","add","valueAt","total"]arguments = [[1],[0,0,5],[0],[],[0,0,-8],[0],[]]
- Output:
- [null,null,5,5,null,-3,-3]
- Explanation:
The single cell goes from 5 to -3 after adding -8, and the total always equals that one value.
Example 3
- Input:
- operations = ["SpanAdjuster","total","add","valueAt","valueAt","valueAt","total"]arguments = [[3],[],[1,2,-4],[0],[1],[2],[]]
- Output:
- [null,0,null,0,-4,-4,-8]
- Explanation:
Adding -4 to positions 1 and 2 leaves the values 0, -4, -4, so the total is -8.
Constraints
-
1 ≤ n ≤ 105 -
at most 2000 calls in total -
0 ≤ left ≤ right < n -
0 ≤ index < n -
-106 ≤ delta ≤ 106
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.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) per call
- Space
- O(n)