Dynamic Range Maximum
In many real-world applications, such as financial trading platforms, sensor data analysis, or game development, we often need to efficiently track and update values over dynamic ranges. For instance, imagine a system monitoring stock prices where a certain event might cause all stocks in a particular sector to increase by a fixed percentage, and you frequently need to find the highest price within a given portfolio range. This problem challenges you to design a data structure that can handle both range updates (adding a value to all elements within a specified range) and range queries (finding the maximum value within a specified range) efficiently.
Implement a class DynamicRangeMaximum that supports the following operations:
updateRange(left, right, value): Adds value to each element in the array from index left to right (inclusive).queryMax(left, right): Returns the maximum value among elements in the array from index left to right (inclusive).Your solution should provide optimal time complexity for both update and query operations.
DynamicRangeMaximum(initialArray: number[])initialArray: An array of numbers representing the initial state of the data. Its length N can be up to 10^5.updateRange(left: number, right: number, value: number): voidleft: The starting index of the range (0-indexed).right: The ending index of the range (0-indexed).value: The number to be added to all elements within the range [left, right].queryMax(left: number, right: number): numberleft: The starting index of the range (0-indexed).right: The ending index of the range (0-indexed).[left, right].left, right) are 0-based and inclusive.0 <= left <= right < N for all updateRange and queryMax calls.value in updateRange can be positive, negative, or zero.initialArray will not be empty.Examples
Example 1
Input:
operations = ["DynamicRangeMaximum","queryMax","updateRange","queryMax","queryMax","updateRange","queryMax"], params = [[[1,2,3,4,5]],[0,4],[0,2,10],[0,1],[0,4],[3,4,-5],[2,4]]
Output:
[null,5,null,12,13,null,13]
Note:
[1,2,3,4,5].queryMax(0,4): Max of [1,2,3,4,5] is 5.updateRange(0,2,10): Array becomes [11,12,13,4,5].queryMax(0,1): Max of [11,12] is 12.queryMax(0,4): Max of [11,12,13,4,5] is 13.updateRange(3,4,-5): Array becomes [11,12,13,-1,0].queryMax(2,4): Max of [13,-1,0] is 13.Example 2
Input:
operations = ["DynamicRangeMaximum","updateRange","queryMax","updateRange","queryMax"], params = [[[10]],[0,0,-5],[0,0],[0,0,20],[0,0]]
Output:
[null,null,5,null,25]
Note:
[10].updateRange(0,0,-5): Array becomes [5].queryMax(0,0): Max of [5] is 5.updateRange(0,0,20): Array becomes [25].queryMax(0,0): Max of [25] is 25.Example 3
Input:
operations = ["DynamicRangeMaximum","updateRange","queryMax","updateRange","queryMax"], params = [[[1,1,1,1,1]],[0,4,5],[0,2],[2,4,-2],[0,4]]
Output:
[null,null,6,null,6]
Note:
[1,1,1,1,1].updateRange(0,4,5): Array becomes [6,6,6,6,6].queryMax(0,2): Max of [6,6,6] is 6.updateRange(2,4,-2): Array becomes [6,6,4,4,4].queryMax(0,4): Max of [6,6,4,4,4] is 6.Constraints
1 <= N <= 10^5 (where N is the length of initialArray)-10^9 <= initialArray[i] <= 10^9-1000 <= value <= 1000 for updateRange operations1 <= Q <= 10^5 (where Q is the total number of updateRange and queryMax operations)updateRange and queryMax operations: O(log N)O(N)left, right indices (assume they are always valid).values that could cause integer overflow beyond standard number limits (assume number type is sufficient).Loading editor...