Range Sum Query - Mutable

Problem Statement

The task is to design a class NumArray which initially takes a list of integers nums and allows two main types of operations. The first type of operation involves updating the value of an element in the list at a specific index. The second type of operation is calculating the sum of a subarray defined between two indices left and right where both bounds are inclusive and within the range of the list. The class should efficiently handle multiple queries of both types without unnecessary re-computation, particularly under constraints where the operations and array size can scale significantly.

Examples

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 becomes [1, 2, 5]  
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 10^4 calls will be made to update and sumRange.

Approach and Intuition

To efficiently handle the two operations described—updating an element and querying the sum of a subarray—several data structures and techniques can be considered:

1. Naive Approach

• Update: O(1) — simple assignment at index.
• Sum Query: O(k) — iterate from left to right, worst-case O(n).
• Not scalable for large numbers of operations.

2. Segment Tree

• Construction Time: O(n)

• Update Time: O(log n)

• Query Time: O(log n)

• Details:

  • Store aggregate segment sums in a binary tree structure.
  • Modify only affected segments during update.
  • Efficiently combine relevant segments during sum queries.

3. Binary Indexed Tree (Fenwick Tree)

• Update Time: O(log n)
• Prefix Sum Time: O(log n)
• Range Sum: Calculate as prefixSum(right) - prefixSum(left - 1)
• Less memory overhead than segment tree, but trickier for range queries beyond prefix sum.

Solutions

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