Dynamic Range Sum with Point Updates
In various enterprise applications, such as real-time analytics dashboards or inventory management systems, there's often a need to efficiently query sums over a range of data points while also supporting rapid updates to individual data points. This problem challenges you to implement a data structure that can handle both operations optimally.
You are tasked with implementing a NumArray class that supports two primary operations:
NumArray(nums): Initializes the object with an integer array nums.update(index, val): Updates the value of nums[index] to val.sumRange(left, right): Returns the sum of the elements of nums between indices left and right (inclusive).Your implementation should prioritize efficient execution of both update and sumRange operations.
The NumArray class will be instantiated with an initial array nums.
NumArray(nums: number[]):
nums: An array of integers representing the initial data.void (constructor).update(index: number, val: number): void:
index: The 0-based index of the element to be updated.val: The new value for nums[index].void.sumRange(left: number, right: number): number:
left: The starting 0-based index of the range (inclusive).right: The ending 0-based index of the range (inclusive).nums[i] for left <= i <= right.nums is 0-indexed.left and right indices for sumRange will always be valid and left <= right.index for update will always be a valid index within the current bounds of nums.Examples
Example 1
Input:
operations = ["NumArray","sumRange","update","sumRange"], params = [[[1,3,5]],[0,2],[1,2],[0,2]]
Output:
[null,9,null,8]
Note:
NumArray numArray = new NumArray([1, 3, 5]); // nums = [1, 3, 5] numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
Example 2
Input:
operations = ["NumArray","update","sumRange","update","sumRange"], params = [[[7,2,7,2,0]],[4,6],[0,4],[0,9],[0,4]]
Output:
[null,null,24,null,26]
Note:
NumArray numArray = new NumArray([7, 2, 7, 2, 0]); // initial nums numArray.update(4, 6); // nums becomes [7, 2, 7, 2, 6] numArray.sumRange(0, 4); // return 7 + 2 + 7 + 2 + 6 = 24 numArray.update(0, 9); // nums becomes [9, 2, 7, 2, 6] numArray.sumRange(0, 4); // return 9 + 2 + 7 + 2 + 6 = 26
Example 3
Input:
operations = ["NumArray","sumRange","update","update","sumRange","sumRange"], params = [[[0,9,5,7,3]],[4,4],[1,6],[0,10],[1,2],[1,4]]
Output:
[null,3,null,null,11,21]
Note:
NumArray numArray = new NumArray([0, 9, 5, 7, 3]); // initial nums numArray.sumRange(4, 4); // return nums[4] = 3 numArray.update(1, 6); // nums becomes [0, 6, 5, 7, 3] numArray.update(0, 10); // nums becomes [10, 6, 5, 7, 3] numArray.sumRange(1, 2); // return nums[1] + nums[2] = 6 + 5 = 11 numArray.sumRange(1, 4); // return nums[1] + nums[2] + nums[3] + nums[4] = 6 + 5 + 7 + 3 = 21
Constraints
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length3 * 10^4 calls will be made to update and sumRange.10^5.update and sumRange operations.Loading editor...