Range Sum Query - Mutable

LeetCode 307 | Difficulty: Medium

Medium

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** (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 * 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`.

Topics: Array, Divide and Conquer, Design, Binary Indexed Tree, Segment Tree

---

Approach

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 160 ms)

Metric	Value
Runtime	160 ms
Memory	37.9 MB
Date	2020-02-10

Solution

public class NumArray {

    int[] nums;
    int[] BIT;
    int n;

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

        n = nums.Length;
        BIT = new int[n + 1];
        for (int i = 0; i < n; i++)
            init(i, nums[i]);
    }

    public void init(int i, int val)
    {
        i++;
        while (i <= n)
        {
            BIT[i] += val;
            i += (i & -i);
        }
    }

    public void Update(int i, int val)
    {
        int diff = val - nums[i];
        nums[i] = val;
        init(i, diff);
    }

    public int getSum(int i)
    {
        int sum = 0;
        i++;
        while (i > 0)
        {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }

    public int SumRange(int i, int j)
    {
        return getSum(j) - getSum(i - 1);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.Update(i,val);
 * int param_2 = obj.SumRange(i,j);
 */

📜 1 more C# submission(s)

Submission (2020-02-08) — 504 ms, 37.8 MB

public class NumArray {

    int[] dp;

    public NumArray(int[] nums)
    {
        dp = new int[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++)
        {
            dp[i + 1] = dp[i] + nums[i];
        }
    }

    public void Update(int i, int val)
    {
        int curVal = dp[i+1]-dp[i];
        int diff = val-curVal;
        for (int j = i+1; j < dp.Length; j++)
        {
            dp[j] += diff;
        }
    }

    public int SumRange(int i, int j)
    {
        return dp[j+1]-dp[i];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.Update(i,val);
 * int param_2 = obj.SumRange(i,j);
 */

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify the expected time complexity for each operation before choosing data structures.