307 Range Sum Query - Mutable - Algorithm Practice

307. Range Sum Query - Mutable​
1. Question
Given an integer arraynums, find the sum of the elements between indicesiandj(i≤j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
1
Given nums = [1, 3, 5]
2
​
3
sumRange(0, 2) -> 9
4
update(1, 2)
5
sumRange(0, 2) -> 8
Copied!
Note:
1.The array is only modifiable by the update function.
2.You may assume the number of calls to update and sumRange function is distributed evenly.
2. Implementation
(1) Binary Index Tree
1
class NumArray {
2
    BIT bit;
3
    int[] nums;
4
    int size;
5
​
6
    public NumArray(int[] nums) {
7
        if (nums == null || nums.length == 0) {
8
            return ;
9
        }
10
        size = nums.length;
11
        this.nums = nums;
12
        bit = new BIT(size);
13
​
14
        for (int i = 0; i < size; i++) {
15
            bit.update(i + 1, nums[i]);
16
        }
17
    }
18
​
19
    public void update(int i, int val) {
20
        bit.update(i + 1, val - nums[i]);
21
        nums[i] = val;
22
    }
23
​
24
    public int sumRange(int i, int j) {
25
        return bit.query(j + 1) - bit.query(i);
26
    }
27
}
28
​
29
class BIT {
30
    int[] sums;
31
​
32
    public BIT(int n) {
33
        sums = new int[n + 1];
34
    }
35
​
36
    public void update (int index, int val) {
37
        while (index < sums.length) {
38
            sums[index] += val;
39
            index += index & -index;
40
        }
41
    }
42
​
43
    public int query(int index) {
44
        int sum = 0;
45
        while (index > 0) {
46
            sum += sums[index];
47
            index -= index & -index;
48
        }
49
        return sum;
50
    }
51
}
52
​
53
/**
54
 * Your NumArray object will be instantiated and called as such:
55
 * NumArray obj = new NumArray(nums);
56
 * obj.update(i,val);
57
 * int param_2 = obj.sumRange(i,j);
58
 */
Copied!
3. Time & Space Complexity
Binary Indexed Tree: 时间复杂度: Binary Indexed Tree构造O(NlogN), update(logN), sumRange(logN), 空间复杂度O(N)

587 Erect the Fence

308 Range Sum Query 2D - Mutable

Last modified 2yr ago

Copy link

Contents

307. Range Sum Query - Mutable

1. Question

2. Implementation

3. Time & Space Complexity

307. Range Sum Query - Mutable​

1. Question

2. Implementation

3. Time & Space Complexity

307. Range Sum Query - Mutable