Range Sum Query - Mutable

MEDIUM

Description

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

Update the value of an element in nums.
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 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 10⁴ calls will be made to update and sumRange.

Approaches

Checkout 4 different approaches to solve Range Sum Query - Mutable. Click on different approaches to view the approach and algorithm in detail.

Brute Force

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

Constructor NumArray(int[] nums):
- Initialize a member variable, an integer array, with the values from the input nums.
Update update(int index, int val):
- Directly access the element at the given index in the stored array and set its value to val.
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.

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 Analysis

Time Complexity: * **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 Complexity: O(N), where N is the number of elements in the input array. This space is used to store the copy of the array.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Range Sum Query - Mutable. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Range Sum Query - Mutable

Patterns:

Design

Data Structures:

ArrayBinary Indexed TreeSegment Tree

Companies:

Google |