Fork me on GitHub

Range Sum Query - Mutable

Posted on

Description

https://leetcode.com/problems/range-sum-query-mutable/description/

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
class NumArray {
private:
    vector<int> tree;
    int size;
public:
    NumArray(vector<int> nums) {
        size = nums.size();
        if (size == 0) return;
        tree.resize(size * 10);
        buildTree(nums, 0, 0, size - 1);
    }
    
    void buildTree(vector<int>& nums, int treeIndex, int left, int right) {
        if (left == right) {    
            tree[treeIndex] = nums[left];
            return;
        };
        int mid = (right - left) / 2 + left;
        buildTree(nums, treeIndex * 2 + 1, left, mid);
        buildTree(nums, treeIndex * 2 + 2, mid + 1, right);
        tree[treeIndex] = tree[treeIndex * 2 + 1] + tree[treeIndex * 2 + 2];
        
        return;
    }
    
    void update(int i, int val) {
        updateST(i, val, 0, size - 1, 0);
    }
    
    void updateST(int index, int val, int left, int right, int treeIndex) {
        if (left == right) {tree[treeIndex] = val; return;}
        
        int mid = left + (right - left) / 2;
        if (index > mid) 
            updateST(index, val, mid + 1, right, treeIndex * 2 + 2);
        else 
            updateST(index, val, left, mid, treeIndex * 2 + 1);
        
        tree[treeIndex] = tree[treeIndex * 2 + 1] + tree[treeIndex * 2 + 2];
        
        return;
    }
    
    int sumRange(int i, int j) {
        int ret = sumRangeST(i, j, 0, 0, size - 1);
        // cout << ret << endl;
        return ret;
    }
    
    int sumRangeST(int targetLeft, int targetRight, int treeIndex, int currentLeft, int currentRight) {
        if (targetLeft == currentLeft 
                && targetRight == currentRight) 
            return tree[treeIndex];
        
        int mid = currentLeft + (currentRight - currentLeft) / 2;
        
        int left = 0;
        int right = 0;
        
        if (targetLeft <= mid) 
            left = sumRangeST(targetLeft, min(targetRight, mid), 
                              treeIndex * 2 + 1, currentLeft, mid);min(mid, targetRight);
        if (targetRight >= mid + 1) 
            right = sumRangeST(max(mid + 1, targetLeft), targetRight, treeIndex * 2 + 2, mid + 1, currentRight);
        

        return left + right;
    }
};

/**
 * 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);
 */