Scale Engineer

Range Sum Query - Mutable

Med
#0294Time: * **Constructor**: O(N) to create a copy of the input array. * **`update`**: O(1) as it's a direct array access. * **`sumRange`**: O(N) in the worst case, as we might need to iterate through the entire array.Space: O(N), where N is the number of elements in the input array. This space is used to store the copy of the array.1 company
Patterns
Design
Data structures
ArrayBinary Indexed TreeSegment Tree
Companies
Google

Prompt

Given an integer array nums, handle multiple queries of the following types:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

 

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([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

 

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the operations directly on the array. We store a copy of the input array nums. When an update is requested, we modify the element at the specific index. When a sum range is requested, we iterate through the given range and calculate the sum on the fly.

Algorithm

  1. Constructor NumArray(int[] nums):
    • Initialize a member variable, an integer array, with the values from the input nums.
  2. Update update(int index, int val):
    • Directly access the element at the given index in the stored array and set its value to val.
  3. Sum Range sumRange(int left, int right):
    • Initialize a variable sum to 0.
    • Loop from left to right (inclusive).
    • In each iteration, add the value of the element nums[i] to sum.
    • Return the final sum.

Walkthrough

In this approach, the NumArray class holds a copy of the integer array. The update operation is efficient as it only involves a single array modification, which is a constant time operation. However, the sumRange operation requires iterating through all the elements from the left index to the right index. In the worst-case scenario, where the range covers the entire array, this iteration takes time proportional to the size of the array, N.

class NumArray {    private int[] nums;     public NumArray(int[] nums) {        this.nums = nums;    }        public void update(int index, int val) {        nums[index] = val;    }        public int sumRange(int left, int right) {        int sum = 0;        for (int i = left; i <= right; i++) {            sum += nums[i];        }        return sum;    }}

Complexity

Time

* **Constructor**: O(N) to create a copy of the input array. * **`update`**: O(1) as it's a direct array access. * **`sumRange`**: O(N) in the worst case, as we might need to iterate through the entire array.

Space

O(N), where N is the number of elements in the input array. This space is used to store the copy of the array.

Trade-offs

Pros

  • Very simple to understand and implement.

  • The update operation is extremely fast, taking O(1) time.

  • Requires minimal extra space, just enough to store the array itself.

Cons

  • The sumRange operation is very slow, with a time complexity of O(N) in the worst case.

  • This approach will likely result in a 'Time Limit Exceeded' error for large inputs and a high number of sumRange queries, as specified in the problem constraints.

Solutions

class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void Update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } public int Query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } public class NumArray { private BinaryIndexedTree tree ; public NumArray ( int [] nums ) { int n = nums . Length ; tree = new BinaryIndexedTree ( n ); for ( int i = 0 ; i < n ; ++ i ) { tree . Update ( i + 1 , nums [ i ]); } } public void Update ( int index , int val ) { int prev = SumRange ( index , index ); tree . Update ( index + 1 , val - prev ); } public int SumRange ( int left , int right ) { return tree . Query ( right + 1 ) - tree . Query ( left ); } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.Update(index,val); * int param_2 = obj.SumRange(left,right); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem