Range Sum Query Mutable - Leetcode Solution

Problem:

Given an array nums and two types of queries where:

1. Update a value in the array 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:

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 9 = sum([1,3,5])
• numArray.update(1, 2); // nums = [1,2,5]
• numArray.sumRange(0, 2); // return 8 = sum([1,2,5])

Solution:

We can use the concept of segment tree to solve this problem. The idea is to construct a binary tree where the nodes represent the different segments of the array and each node stores the sum of the elements in that segment. The root node represents the entire array and its left child represents the left half of the array and its right child represents the right half of the array. We can recursively construct this tree by dividing the array into two halves until we reach the base case when there is only one element in the array.

We can also update the values in the array by traversing the tree and updating the values at the corresponding nodes.

To calculate the sum of the elements between two indices, we traverse down the tree and calculate the sum of the segments that overlap with the given range.

The time complexity of constructing the tree and updating the values is O(n log n) and the time complexity of calculating the range sum is O(log n).

Here is the Java implementation of the NumArray class:

class NumArray { int[] nums; int[] tree; int n;

public NumArray(int[] nums) {
    this.nums = nums;
    n = nums.length;
    tree = new int[4 * n];
    buildTree(0, 0, n - 1);
}

private void buildTree(int node, int start, int end) {
    if (start == end) {
        tree[node] = nums[start];
    } else {
        int mid = (start + end) / 2;
        buildTree(2 * node + 1, start, mid);
        buildTree(2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

public void update(int index, int val) {
    updateTree(0, 0, n - 1, index, val);
}

private void updateTree(int node, int start, int end, int index, int val) {
    if (start == end) {
        nums[index] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (start <= index && index <= mid) {
            updateTree(2 * node + 1, start, mid, index, val);
        } else {
            updateTree(2 * node + 2, mid + 1, end, index, val);
        }
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
}

public int sumRange(int left, int right) {
    return queryTree(0, 0, n - 1, left, right);
}

private int queryTree(int node, int start, int end, int left, int right) {
    if (right < start || end < left) {
        return 0;
    } else if (left <= start && end <= right) {
        return tree[node];
    } else {
        int mid = (start + end) / 2;
        int sumLeft = queryTree(2 * node + 1, start, mid, left, right);
        int sumRight = queryTree(2 * node + 2, mid + 1, end, left, right);
        return sumLeft + sumRight;
    }
}

}

We create a class NumArray that has a constructor that initializes the tree with the given array nums. We use the buildTree method to construct the tree recursively.

We also have a method update that is used to update the values in the array. We use the updateTree method to traverse the tree and update the values at the corresponding nodes.

We have a method sumRange that is used to calculate the sum of the elements between two indices. We use the queryTree method to traverse the tree and calculate the sum of the segments that overlap with the given range.

We traverse the tree by comparing the given range with the segments that each node represents. If the given range does not overlap with the segment represented by a node, we return 0. If the given range is completely inside the segment represented by a node, we return the value of that node. Otherwise, we traverse down the left and right children of the node and calculate the sum of the segments that overlap with the given range. We return the sum of the left and right segments.

We create an instance of the NumArray class and call the sumRange and update methods as required. The time complexity of constructing the tree and updating the values is O(n log n) and the time complexity of calculating the range sum is O(log n).

1