Range Sum Query — Mutable

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

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

Approach: Segment Tree

Algorithm

1. Build a segment tree from the input array, where each node stores the sum of its segment
2. Each leaf holds a single element; each internal node holds the sum of its two children
3. To update, walk from the leaf that contains index up to the root, recomputing node sums
4. To query, combine the node sums that exactly cover [left, right], pruning branches fully outside or inside the range
5. Both update and sumRange take O(log n), improving on the O(n) prefix-array rebuild

Time & Space Complexity

• Time Complexity: O(log n) per update and sumRange; O(n) for the initial build
• Space Complexity: O(n) - the segment tree array uses roughly 4 * n entries

Java Implementation

public class NumArray {

    private final int[] tree;
    private final int n;

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

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

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

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

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

    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        return query(2 * node, start, mid, l, r)
                + query(2 * node + 1, mid + 1, end, l, r);
    }

    // Test method
    public static void main(String[] args) {
        NumArray numArray = new NumArray(new int[]{1, 3, 5});
        System.out.println("sumRange(0, 2): " + numArray.sumRange(0, 2)); // Expected: 9
        numArray.update(1, 2); // nums = [1, 2, 5]
        System.out.println("sumRange(0, 2): " + numArray.sumRange(0, 2)); // Expected: 8
    }
}

Example Walkthrough

For nums = [1, 3, 5]:

1. The segment tree stores sums over segments: [0,2] -> 9, [0,1] -> 4, [2,2] -> 5, [0,0] -> 1, [1,1] -> 3
2. sumRange(0, 2) returns the root sum 9
3. update(1, 2) changes the leaf at index 1 to 2, then recomputes [0,1] -> 3 and the root -> 8
4. sumRange(0, 2) now returns 8

Key Points

1. Segment Tree: A balanced binary tree where every node stores an aggregate (sum) of its segment
2. Point Update: Only O(log n) ancestors of the updated leaf need recomputation
3. Range Query: Decomposes [left, right] into O(log n) disjoint canonical nodes
4. 4 * n Size: Indexing by 2 * node and 2 * node + 1 needs a 4 * n sized array to avoid out-of-bounds
5. O(log n): Both operations beat the O(n) rebuild of a naive prefix-sum array