307. Range Sum Query - Mutable

tip

Practice this problem live on: LeetCode 307. Range Sum Query - Mutable

Problem Statement

Click to expand the full LeetCode problem description

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:

• $\mathtt{1 \le nums.length \le 3 \times 10^4}$
• $\mathtt{-100 \le nums[i] \le 100}$
• $\mathtt{0 \le index < nums.length}$
• $\mathtt{-100 \le val \le 100}$
• $\mathtt{0 \le left \le right < nums.length}$
• At most $\mathtt{3 \times 10^4}$ calls will be made to update and sumRange.

Approach 1: Straightforward Simulation (Brute Force)

Intuition and Logic

When we first read the problem, we notice it asks us to perform two operations on an array: modify a value and calculate a range sum. The most intuitive way to solve this is to follow the problem description literally, treating it as two independent tasks.

Operation 1: The Update Operation (update(index, val))

Our intuition here is as simple as it gets: we do not need to shift any neighboring elements or rebuild any complex structure. We just pinpoint the exact position in the array and overwrite the old data with the new value.

Logically, this is a direct, single-step assignment:

$$\mathtt{nums[index] = val}$$

Since we can access any element in an array instantly ($O(1)$) if we know its index, this logic hints that the update operation will be incredibly fast.

Operation 2: The Range Sum Operation (sumRange(left, right))

If we are given a range [left, right], the natural instinct is to start a counter at left and add every element one by one until we reach right.

Mathematically, this means we are computing:

$$\text{sum}(\mathtt{left}, \mathtt{right}) = \mathtt{nums}[\mathtt{left}] + \mathtt{nums}[\mathtt{left} + 1] + \dots + \mathtt{nums}[\mathtt{right}]$$

To translate this into logic, we need:

• An accumulator variable (e.g. sum) initialized to 0
• A simple loop that iterates index i from left to right (inclusive) to pile up the values.

This brute-force approach requires zero pre-processing or complex formulas. It represents the natural baseline of our thoughts. Let's see how we translate both the update and sum logic into actual code across different languages in the next section.

Implementation

Java

class NumArray {
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public void update(int index, int val) {
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum = sum + nums[i];
        }
        return sum;
    }
}

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(index,val);
* int param_2 = obj.sumRange(left,right);
*/

Java Implementation Details & Design Mechanics

1. Instance Variable (int[] nums) - State Persistence [Line 2]

   • The Detail: Declared at the class level to persist the array's data state across multiple independent method calls.
   • The Logic: If we were to load the array locally inside the constructor, that variable would be destroyed the moment initialization ended. Elevating it to a class member variable ensures that subsequent calls to update() and sumRange() are always interacting with the exact same dataset.

2. Data Flow in Constructor (this.nums = nums;) - Reference Copy [Line 5]

   • The Detail: Inside the constructor, we map the incoming parameter to our instance variable using the this keyword.
   • The Logic: In Java, this.nums = nums; performs a reference (pointer) copy in $O(1)$ time rather than an element-by-element deep copy. This efficiently anchors our class object to the data source provided by the system.

Complexity Analysis

Time Complexity

• update() Operation: $O(1)$. Overwriting a value at a specific index in an array is a direct memory access operation, which executes in constant time.
• sumRange() Operation: $O(n)$. In the worst-case scenario (where left = 0 and right = n - 1), the loop must iterate through all $n$ elements to calculate the cumulative sum.

Space Complexity

• Overall Space: $O(n)$, where $n$ is the length of the input array nums.
• The Detail: We do not allocate additional memory to deep-copy the array. However, our instance variable this.nums maintains a reference to the original data source to persist the object's state, which scales linearly with the input size.

Bottleneck Analysis

The performance bottleneck of this brute-force design is driven by two interdependent factors: the input array size ($n$) and the total number of method calls ($m$).

Generally, LeetCode's modern judging platform enforces an execution limit of approximately $10^6 \sim 10^7$ operations per submission. According to the problem constraints:

• The maximum array length is $n = 3 \times 10^4$.
• The maximum number of total calls to update and sumRange is $m = 3 \times 10^4$.

Let's evaluate the total workload under the worst-case scenario:

1. update() Workload Evaluation

$$\begin{aligned} \text{Total Time} &= \text{Single Call Complexity} \times \text{Number of Calls} \\ &= O(1) \times (3 \times 10^4) \\ &= 3 \times 10^4 \ \text{operations} \\ \end{aligned}$$

• Verdict: Well below the platform limit. The update() method is fully optimized.

2. sumRange() Workload Evaluation

$$\begin{aligned} \text{Total Time} &= \text{Single Call Complexity} \times \text{Number of Calls} \\ &= O(n) \times m \\ &= (3 \times 10^4) \times (3 \times 10^4) \\ &= 9 \times 10^8 \ \text{operations} \\ \end{aligned}$$

• Verdict: Since $9 \times 10^8$ significantly exceeds the standard $10^6 \sim 10^7$ threshold, this operation will inevitably trigger a Time Limit Exceeded (TLE) error.

Submission Results

• Status: Time Limit Exceeded (TLE)
• Testcases Passed: 15 / 16 testcases passed

Note from the Author: As predicted in the Bottleneck Analysis, the brute-force approach successfully passes 15 testcases but inevitably chokes on the final, large-scale dataset. This empirical failure confirms that an $O(n)$ query complexity is unacceptable under strict time constraints, perfectly setting the stage for our next optimization.

What's Next?

The core bottleneck of Approach 1 is that sumRange() has to re-sum the elements from scratch every single time, performing redundant calculations over overlapping sub-arrays.

Click to see an example of redundant calculations

Imagine we have an array nums = [1, 2, 3, 4, 5], and the user makes the following successive query calls:

1. sumRange(1, 4) $\rightarrow$ Calculates 2 + 3 + 4 + 5
2. sumRange(2, 4) $\rightarrow$ Calculates $\quad\ \,$ 3 + 4 + 5
3. sumRange(1, 3) $\rightarrow$ Calculates 2 + 3 + 4

Notice how the sub-array [3, 4] (elements at indices 2 and 3) is being repeatedly scanned and added up in every single call. When the array size scales up to $3 \times 10^4$ and millions of queries overlap, these redundant traversals will completely freeze the CPU, leading to the TLE we saw above.

To optimize this, we need a way to "remember" the accumulated sums we have already calculated. Imagine if we could pre-calculate the total sum from the very beginning up to every possible index.

This introduces our next optimization strategy for this classic Range Sum Query (RSQ) problem: Prefix Sum, which aims to trade a tiny bit of space to slash the query time from $O(n)$ down to a staggering $O(1)$.

Stay tuned!
Approach 2 (Prefix Sum) and advanced dynamic trees (Segment Tree and Fenwick Tree [i.e., Binary Indexed Tree/BIT]) are actively under construction.