lc307-Range Sum Query - Mutable

發表於   |   分類於   |   0 comments   |  

standard segment tree

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
struct node {
    node * left = nullptr;
    node * right = nullptr;
    int down, up;
    int val = 0;
    node(int l, int u):up(u),down(l) {}
};
class NumArray {
    int size;
    node* root;
public:
    node* buildTree(int l, int u, vector<int> &nums) {
        node* r = new node(l, u);
        if (l == u) {
            r->val = nums[l];
            return r;
        }
        if ((l+u)/2 >= l)
            r->left = buildTree(l, (l+u)/2, nums);
        if ((l+u)/2+1 <= u)
            r->right = buildTree((l+u)/2+1, u, nums);
        r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        return r;
    }
    
    void updateTree(int i, int val, node* r) {
        if (r->down == r->up) {
            r->val = val;
            return;
        }
        int mid = (r->down + r->up)/2;
        if (mid >= i) {
            updateTree(i, val, r->left);
            r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        }
        else {
            updateTree(i, val, r->right);
            r -> val = ((r->left)?r->left->val:0) + ((r->right)?r->right->val:0);
        }
    }
    
    int sumRangeFromTree(node* r, int l, int u, int i, int j) {
        if (l == i && u == j)
            return r->val;
        else {
            int m = (l+u)/2;
            int s1 = (i<=m)?sumRangeFromTree(r->left, l, m, i, min(j,m)):0;
            int s2 = (j>m)?sumRangeFromTree(r->right, m+1, u, max(i,m+1), j):0;
            return s1+s2;
        }
    }
    
    NumArray(vector<int> &nums) {
        this->size = nums.size();
        if (this->size)
            this->root = buildTree(0, this->size-1, nums);
    }
    
    void update(int i, int val) {
        updateTree(i, val, this->root);
    }
    
    int sumRange(int i, int j) {
        return sumRangeFromTree(this->root, 0, size-1, i, j);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);