307. Range Sum Query - Mutable

Jump to Solution: Python Java C++ JavaScript C#

Problem 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.

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.

Solution

Python Solution

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        
        # Build the tree
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]

    def update(self, index: int, val: int) -> None:
        # Get to the leaf
        pos = self.n + index
        
        # Update the value
        self.tree[pos] = val
        
        # Update parent nodes
        while pos > 1:
            left = pos
            right = pos
            if pos % 2 == 0:
                right = pos + 1
            else:
                left = pos - 1
            self.tree[pos // 2] = self.tree[left] + self.tree[right]
            pos //= 2

    def sumRange(self, left: int, right: int) -> int:
        # Get leaf with left and right
        left += self.n
        right += self.n
        
        sum = 0
        while left <= right:
            if left % 2 == 1:
                sum += self.tree[left]
                left += 1
            if right % 2 == 0:
                sum += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
            
        return sum

Time Complexity:

Constructor: O(n)
update: O(log n)
sumRange: O(log n)

Space Complexity: O(n)

For storing the segment tree.

Java Solution

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

    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[2 * n];
        
        // Build the tree
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2*i] + tree[2*i + 1];
        }
    }
    
    public void update(int index, int val) {
        // Get to the leaf
        int pos = n + index;
        
        // Update the value
        tree[pos] = val;
        
        // Update parent nodes
        while (pos > 1) {
            int left = pos;
            int right = pos;
            if (pos % 2 == 0) {
                right = pos + 1;
            } else {
                left = pos - 1;
            }
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }
    
    public int sumRange(int left, int right) {
        // Get leaf with left and 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;
    }
}

Time Complexity:

Constructor: O(n)
update: O(log n)
sumRange: O(log n)

Space Complexity: O(n)

For storing the segment tree.

C++ Solution

class NumArray {
private:
    vector tree;
    int n;
    
public:
    NumArray(vector& nums) {
        n = nums.size();
        tree.resize(2 * n);
        
        // Build the tree
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2*i] + tree[2*i + 1];
        }
    }
    
    void update(int index, int val) {
        // Get to the leaf
        int pos = n + index;
        
        // Update the value
        tree[pos] = val;
        
        // Update parent nodes
        while (pos > 1) {
            int left = pos;
            int right = pos;
            if (pos % 2 == 0) {
                right = pos + 1;
            } else {
                left = pos - 1;
            }
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }
    
    int sumRange(int left, int right) {
        // Get leaf with left and 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;
    }
};

Time Complexity:

Constructor: O(n)
update: O(log n)
sumRange: O(log n)

Space Complexity: O(n)

For storing the segment tree.

JavaScript Solution

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.n = nums.length;
    this.tree = new Array(2 * this.n).fill(0);
    
    // Build the tree
    for (let i = 0; i < this.n; i++) {
        this.tree[this.n + i] = nums[i];
    }
    for (let i = this.n - 1; i > 0; i--) {
        this.tree[i] = this.tree[2*i] + this.tree[2*i + 1];
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function(index, val) {
    // Get to the leaf
    let pos = this.n + index;
    
    // Update the value
    this.tree[pos] = val;
    
    // Update parent nodes
    while (pos > 1) {
        let left = pos;
        let right = pos;
        if (pos % 2 === 0) {
            right = pos + 1;
        } else {
            left = pos - 1;
        }
        this.tree[Math.floor(pos / 2)] = this.tree[left] + this.tree[right];
        pos = Math.floor(pos / 2);
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function(left, right) {
    // Get leaf with left and right
    left += this.n;
    right += this.n;
    
    let sum = 0;
    while (left <= right) {
        if (left % 2 === 1) {
            sum += this.tree[left];
            left++;
        }
        if (right % 2 === 0) {
            sum += this.tree[right];
            right--;
        }
        left = Math.floor(left / 2);
        right = Math.floor(right / 2);
    }
    
    return sum;
};

Time Complexity:

Constructor: O(n)
update: O(log n)
sumRange: O(log n)

Space Complexity: O(n)

For storing the segment tree.

C# Solution

public class NumArray {
    private int[] tree;
    private int n;

    public NumArray(int[] nums) {
        n = nums.Length;
        tree = new int[2 * n];
        
        // Build the tree
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2*i] + tree[2*i + 1];
        }
    }
    
    public void Update(int index, int val) {
        // Get to the leaf
        int pos = n + index;
        
        // Update the value
        tree[pos] = val;
        
        // Update parent nodes
        while (pos > 1) {
            int left = pos;
            int right = pos;
            if (pos % 2 == 0) {
                right = pos + 1;
            } else {
                left = pos - 1;
            }
            tree[pos / 2] = tree[left] + tree[right];
            pos /= 2;
        }
    }
    
    public int SumRange(int left, int right) {
        // Get leaf with left and 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;
    }
}

Time Complexity:

Constructor: O(n)
update: O(log n)
sumRange: O(log n)

Space Complexity: O(n)

For storing the segment tree.

Approach Explanation

The solution uses a Segment Tree data structure:

Key Insight:
- Use segment tree for range queries
- Efficient updates and range sums
- Binary tree representation
- Parent-child relationships
Algorithm Steps:
- Build segment tree
- Update values efficiently
- Calculate range sums
- Maintain tree property

Example walkthrough:

Build tree from array
Update propagates up
Range sum uses tree structure
Logarithmic operations

Alternative approaches:

Binary Indexed Tree
Square Root Decomposition
Sparse Table (static)
Direct array updates

Edge Cases:

Single element array
Full range query
Frequent updates
Large arrays