307. Range Sum Query - Mutable

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]).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class NumArray {
    int[] nums;
    int[] tree;
    int n;
    
    /*
     0,1,2,3,4,5 
    [x,x,8,1,3,5]
    
    
     9
   1   8
  0 1 3 5
    
    */
    public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        this.tree = new int[2 * n];
        
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }
        
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[i * 2] + tree[2 * i + 1];
        }
        
        // System.out.println(Arrays.toString(nums));
        // System.out.println(Arrays.toString(tree));
    }
    
    public void update(int index, int val) {
        nums[index] = val;
        index += n;
        tree[index] = val;
        while (index > 0) {
            int left = index;
            int right = index;
            
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            tree[index / 2] = tree[left] + tree[right];
            index = index / 2;
        }
        // System.out.println(Arrays.toString(nums));
        // System.out.println(Arrays.toString(tree));
    }
    
    public int sumRange(int left, int right) {
        left += n;
        right += n;
        int sum = 0;
        
        while (left <= right) {
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
                continue;
            }
            
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
                continue;
            }
            
            right /= 2;
            left /= 2;
        }
        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);
 */

Solution#

Solution