Frontend School

Range Sum Query - Mutable

DSA
easy

Range Sum Query - Mutable

Easy
Segment Tree
Arrays
Data Structures

Overview

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.

What you need to do / Task

Implement the NumArray class, which supports two primary operations:

  1. NumArray(nums): Initializes the object with an integer array nums.
  2. update(index, val): Updates the value of nums[index] to val.
  3. 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.

Input & output

NumArray(nums: number[])

  • nums: An array of integers representing initial metric values.
  • Returns: 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].
  • Returns: 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).
  • Returns: The sum of nums[left] through nums[right].

Clarifications

  • The left index will always be less than or equal to the right index for sumRange calls.
  • All indices (index, left, right) will be valid and within the bounds of the array nums.

Examples

1

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

2

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

Constraints & assumptions

  • n == nums.length
  • 1 <= n <= 10^3
  • -100 <= nums[i] <= 100
  • 0 <= index < n
  • -100 <= val <= 100
  • 0 <= left <= right < n
  • At most 10^4 calls will be made to update and sumRange.

Out of scope

  • Lazy propagation is not required for this problem, as updates are point-based rather than range-based.

What interviewers evaluate

  • Correctness: The implementation must produce accurate sums for all valid range queries and correctly update array elements.
  • Efficiency: Operations update and sumRange should complete in logarithmic time complexity with respect to the array size.
  • Data Structure Design: The candidate should demonstrate appropriate use and implementation of a Segment Tree (or similar structure) to meet efficiency requirements.
  • Code Quality: The solution should be well-structured, readable, and handle basic edge cases gracefully.

Loading editor...