307. Range Sum Query - Mutable

Explanation:

To efficiently handle multiple queries of updating elements and calculating range sums, we can use a segment tree data structure. The segment tree allows us to perform updates and queries in logarithmic time complexity.

Segment Tree Construction: We will construct a segment tree where each node represents a range of elements in the input array. The leaf nodes will store individual elements of the array, and each internal node will store the sum of its children nodes.
Updating a Value: To update a value at a specific index, we will traverse the segment tree to find the corresponding leaf node and update its value. As we move up the tree, we will also update the parent nodes' sums accordingly.
Calculating Range Sum: To calculate the sum of elements between two indices, we will traverse the segment tree while comparing the query range with each node's range. If a node's range is completely within the query range, we can directly add its sum to the result. If the node's range overlaps with the query range, we will recursively search its children nodes.
Time Complexity: The construction of the segment tree takes O(n) time. Updating a value and calculating range sums both have a time complexity of O(log n) due to the tree traversal.
Space Complexity: The segment tree requires O(n) extra space to store the tree nodes.

:

View Leetcode Problem

class NumArray {
    int[] tree;
    int n;

    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[2 * n];
        System.arraycopy(nums, 0, tree, n, n);
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }

    public void update(int index, int val) {
        index += n;
        tree[index] = val;
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            tree[index / 2] = tree[left] + tree[right];
            index /= 2;
        }
    }

    public int sumRange(int left, int right) {
        left += n;
        right += n;
        int sum = 0;
        while (left <= right) {
            if ((left % 2) == 1) {
                sum += tree[left];
                left++;
            }
            if ((right % 2) == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation:

Code Editor (Testing phase)

Improve Your Solution