Range Sum Query Mutable Problem LeetCode

Problem:

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:

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

HINTS:

1.  A trivial solution for Range Sum Query - RSQ(i, j) is to iterate the array from index i to j and sum each element. For range sum query we access each element from the array for constant time and in the worst case we access N elements. Therefore time complexity is O(N). Time complexity of update query is O(1)
2. Intuition: The idea is to split the array in blocks with length of sqrt(n). Then we calculate the sum of each block and store it in auxiliary memory b. To query RSQ(i, j), we will add the sums of all the blocks lying inside and those that partially overlap with range [i ... j].

Algorithm

Figure 1. Range sum query using SQRT decomposition.

As shown in the Figure (1) example above, the array nums' length is 9, which is split into blocks of size sqrt{9}. To get RSQ(1, 7) we add b[1]. It stores the sum of range [3, 5] and partially sums from block 0 and block 2, which are overlapping boundary blocks.

Solution 1 - using trivial technique as mentioned above

Solution 2: