LeetCode 307: Range Sum Query - Mutable Solution

Master LeetCode problem 307 (Range Sum Query - Mutable), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

307. Range Sum Query - Mutable

Medium

Array Design Binary Indexed Tree Segment Tree

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 307 (Range Sum Query - Mutable)?

This page provides optimized solutions for LeetCode problem 307 (Range Sum Query - Mutable) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 307 (Range Sum Query - Mutable)?

The time complexity for LeetCode 307 (Range Sum Query - Mutable) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 307 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 307 in Java, C++, or Python.

Back to LeetCode Solutions