307

Posted on In , Views:

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

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
#define lowbit(x) (x&-x)

vector<int> v, BIT;

class NumArray {
public:
    void build(){
        int cur;
        for(int i=1; i<v.size(); ++i){
            cur = i;
            while(cur < v.size()){
                BIT[cur] += v[i];
                cur += lowbit(cur);
            }
        }
    }

    int sum(int x){
        int total = 0;
        while(x > 0){
            total += BIT[x];
            x -= lowbit(x);
        }
        return total;
    }

    NumArray(vector<int>& nums) {
        v.assign(nums.size()+1, 0);
        BIT.assign(nums.size()+1, 0);
        for(int i=1; i<=nums.size(); ++i) v[i] = nums[i-1];
        build();
    }
    
    void update(int index, int val) {
        ++index;
        int diff = val - v[index];
        v[index] = val;
        while(index < v.size()){
            BIT[index] += diff;
            index += lowbit(index);
        }
    }
    
    int sumRange(int left, int right) {
        return sum(right+1) - sum(left);
    }
};

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