Frontend School

Dynamic Range Sum with Point Updates

DSA
easy

Dynamic Range Sum with Point Updates

Easy
Segment Tree
Arrays
Data Structures

Overview

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.

What you need to do / Task

You are tasked with implementing a NumArray class that 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 prioritize efficient execution of both update and sumRange operations.

Input & output

The NumArray class will be instantiated with an initial array nums.

  • NumArray(nums: number[]):
    • nums: An array of integers representing the initial data.
    • Returns: 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].
    • 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[i] for left <= i <= right.

Clarifications

  • The array 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

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]); // 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

2

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

3

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

Constraints & assumptions

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • At most 3 * 10^4 calls will be made to update and sumRange.
  • The total number of operations (constructor, update, sumRange) will not exceed 10^5.

What interviewers evaluate

  • Correctness: The solution must correctly compute range sums and handle point updates.
  • Efficiency: The solution should achieve logarithmic time complexity for update and sumRange operations.
  • Data Structure Design: Appropriate choice and implementation of the underlying data structure (e.g., Segment Tree).
  • Code Quality: Clean, readable, and well-structured code with proper error handling where applicable (though not strictly required for this problem).

Loading editor...