Code Implementation

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        self.nums = nums[:]
        for i, num in enumerate(nums):
            self._add(i + 1, num)
        
    def _add(self, i, val):
        while i <= self.n:
            self.tree[i] += val
            i += i & -i

    def update(self, i, val):
        diff = val - self.nums[i]
        self.nums[i] = val
        self._add(i + 1, diff)

    def _prefix_sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def sumRange(self, i, j):
        return self._prefix_sum(j + 1) - self._prefix_sum(i)
      

class NumArray {
private:
    vector<int> tree, nums;
    int n;
    void add(int i, int val) {
        while (i <= n) {
            tree[i] += val;
            i += i & -i;
        }
    }
    int prefixSum(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= i & -i;
        }
        return res;
    }
public:
    NumArray(vector<int>& nums_) {
        n = nums_.size();
        tree = vector<int>(n + 1, 0);
        nums = nums_;
        for (int i = 0; i < n; ++i)
            add(i + 1, nums[i]);
    }
    void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        add(i + 1, diff);
    }
    int sumRange(int i, int j) {
        return prefixSum(j + 1) - prefixSum(i);
    }
};
      

class NumArray {
    private int[] tree, nums;
    private int n;
    public NumArray(int[] nums) {
        this.n = nums.length;
        this.tree = new int[n + 1];
        this.nums = nums.clone();
        for (int i = 0; i < n; ++i) {
            add(i + 1, nums[i]);
        }
    }
    private void add(int i, int val) {
        while (i <= n) {
            tree[i] += val;
            i += i & -i;
        }
    }
    private int prefixSum(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= i & -i;
        }
        return res;
    }
    public void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        add(i + 1, diff);
    }
    public int sumRange(int i, int j) {
        return prefixSum(j + 1) - prefixSum(i);
    }
}
      

class NumArray {
    constructor(nums) {
        this.n = nums.length;
        this.tree = new Array(this.n + 1).fill(0);
        this.nums = nums.slice();
        for (let i = 0; i < this.n; ++i) {
            this._add(i + 1, nums[i]);
        }
    }
    _add(i, val) {
        while (i <= this.n) {
            this.tree[i] += val;
            i += (i & -i);
        }
    }
    update(i, val) {
        let diff = val - this.nums[i];
        this.nums[i] = val;
        this._add(i + 1, diff);
    }
    _prefixSum(i) {
        let res = 0;
        while (i > 0) {
            res += this.tree[i];
            i -= (i & -i);
        }
        return res;
    }
    sumRange(i, j) {
        return this._prefixSum(j + 1) - this._prefixSum(i);
    }
}
      

Problem Description

In this problem, you are given an integer array nums. You need to design a data structure that supports two operations efficiently:

• update(i, val): Update the value of nums[i] to val.
• sumRange(i, j): Return the sum of elements between indices i and j (inclusive), that is, nums[i] + nums[i+1] + ... + nums[j].

The challenge is to make both operations as efficient as possible, especially when there are many updates and sum queries. The naive approach of recalculating sums each time is too slow for large arrays and many operations.

Constraints:

• 1 ≤ nums.length ≤ 3 * 10⁴
• Operations can be called up to 3 * 10⁴ times
• Only one valid value per index at a time
• Indices are 0-based

Thought Process

To solve this problem, let's consider the brute-force approach first: For sumRange(i, j), we could iterate from i to j and sum the values. For update(i, val), we simply set nums[i] to val. However, if there are many sumRange queries, this approach becomes too slow because each sum query takes O(n) time in the worst case.

We need a way to quickly compute the sum of any subarray, even after many updates. This leads us to consider data structures that can:

• Efficiently update an element
• Efficiently compute the sum of any range

Solution Approach

We will use a Binary Indexed Tree (Fenwick Tree) for this problem because it is relatively simple to implement and efficient for point updates and prefix sum queries.

• Initialization: Build a Fenwick Tree from the input array. The tree will store cumulative sums in a way that allows us to efficiently update and query prefix sums.
• Update Operation: When update(i, val) is called, we compute the difference between the new value and the old value at index i. We then propagate this difference through the tree using the Fenwick Tree's update algorithm.
• Sum Range Operation: To compute sumRange(i, j), we calculate prefix_sum(j+1) - prefix_sum(i). The prefix sum up to index k is efficiently computed using the Fenwick Tree's query algorithm.
• Why Fenwick Tree? Because both update and sumRange can be performed in O(log n) time, which is efficient enough for the problem's constraints.

Steps:

1. Initialize the Fenwick Tree with the input array values.
2. For update(i, val), update the tree to reflect the change at index i.
3. For sumRange(i, j), use prefix sums to compute the sum between i and j efficiently.

Example Walkthrough

Let's walk through an example with nums = [1, 3, 5].

• Initialization:
  • Build the Fenwick Tree with the values [1, 3, 5].
• sumRange(0, 2):
  • Compute prefix_sum(3) = 1 + 3 + 5 = 9
  • Compute prefix_sum(0) = 0
  • So, sumRange(0,2) = 9 - 0 = 9
• update(1, 2):
  • nums[1] changes from 3 to 2 (difference = -1)
  • Propagate the difference through the Fenwick Tree
• sumRange(0, 2):
  • Compute prefix_sum(3) = 1 + 2 + 5 = 8
  • Compute prefix_sum(0) = 0
  • So, sumRange(0,2) = 8 - 0 = 8

This demonstrates how both updates and range sums work efficiently, regardless of how many times they are called.

Time and Space Complexity

Brute-Force Approach:

• update(i, val): O(1)
• sumRange(i, j): O(n) in the worst case (when i=0, j=n-1)
• This is too slow for large numbers of queries.

• update(i, val): O(log n) — because each update propagates up the tree.
• sumRange(i, j): O(log n) — because each prefix sum query traverses up the tree.
• Space: O(n) — storing the tree and a copy of the original array.

The Fenwick Tree approach is much more efficient, especially for large arrays and many operations.

Summary

The key to efficiently supporting both updates and range sum queries is to use a data structure like the Fenwick Tree (Binary Indexed Tree), which allows both operations in O(log n) time. We avoid the inefficiency of recalculating sums from scratch by maintaining cumulative information in the tree. This approach is simple to implement, highly efficient, and well-suited to problems involving dynamic range queries and updates.