Range Sum Query - Mutable
Browserstack's monitoring infrastructure collects vast amounts of time-series data, such as server CPU utilization, memory usage, or network throughput. For quick diagnostics, engineers often need to query the sum of metrics over specific time windows. Additionally, individual server metrics can be updated in real-time. An efficient data structure is crucial to support both rapid range sum queries and point updates.
Implement the NumArray class, which 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 be optimized for frequent calls to both update and sumRange operations.
NumArray(nums: number[])
nums: An array of integers representing initial metric values.void (constructor).update(index: number, val: number): void
index: The 0-based index of the element to update.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[left] through nums[right].left index will always be less than or equal to the right index for sumRange calls.index, left, right) will be valid and within the bounds of the array 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]); numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9 numArray.update(1, 2); // nums becomes [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
Example 2
Input:
operations = ["NumArray","update","update","sumRange","sumRange"], params = [[[9,-8]],[0,3],[1,-3],[0,1],[1,1]]
Output:
[null,null,null,0,-3]
Note:
NumArray numArray = new NumArray([9, -8]); numArray.update(0, 3); // nums becomes [3, -8] numArray.update(1, -3); // nums becomes [3, -3] numArray.sumRange(0, 1); // return 3 + (-3) = 0 numArray.sumRange(1, 1); // return -3
Constraints
n == nums.length1 <= n <= 10^3-100 <= nums[i] <= 1000 <= index < n-100 <= val <= 1000 <= left <= right < n10^4 calls will be made to update and sumRange.update and sumRange should complete in logarithmic time complexity with respect to the array size.Loading editor...