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.