MyLeetcode/cpp_solutions/307.cpp at main · Kaminyou/MyLeetcode · GitHub

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class BinaryIndexTree {
private:
    vector<int> BIT;
    int n;
public:
    // start from 1
    BinaryIndexTree(vector<int>& nums) {
        n = nums.size(); // [1 ... n]
        BIT = vector<int>(n + 1, 0);
        for (int i = 0; i < n; i++) {
            update(i + 1, nums[i]);
        }
    }
    void update(int index, int value) {
        while (index <= n) {
            BIT[index] += value;
            index += lsb(index);
        }
    }
    int query(int index) {
        int res = 0;
        while (index) {
            res += BIT[index];
            index -= lsb(index);
        }
        return res;
    }
    int lsb(int x) {
        return x & (-x);
    }
};
class NumArray {
public:
    BinaryIndexTree* bit;
    vector<int> numsCache;
    NumArray(vector<int>& nums) {
        bit = new BinaryIndexTree(nums);
        for (auto num : nums) numsCache.push_back(num);
    }

    void update(int index, int val) {
        bit->update(index + 1, val - numsCache[index]);
        numsCache[index] = val;
    }

    int sumRange(int left, int right) {
        return bit->query(right + 1) - bit->query(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);
 */

// V2
// class BIT {
// private:
//     vector<int> tree;
// public:
//     BIT(int size) {
//         tree.resize(size + 1, 0);
//     }
//     int lsb(int x) {
//         return x & (-x);
//     }
//     void add(int index, int value) {
//         while (index < tree.size()) {
//             tree[index] += value;
//             index += lsb(index);
//         }
//     }
//     int querySum(int index) {
//         int sum = 0;
//         while (index) {
//             sum += tree[index];
//             index -= lsb(index);
//         }
//         return sum;
//     }
//     int queryRange(int index1, int index2) {
//         return querySum(index2) - querySum(index1 - 1);
//     }
// };
// class NumArray {
// public:
//     vector<int>* nums;
//     BIT* bit;
//     NumArray(vector<int>& nums) {
//         this->nums = &nums;
//         int n = nums.size();
//         bit = new BIT(n);
//         for (int i = 0; i < nums.size(); ++i) {
//             bit->add(i + 1, nums[i]);
//         }
//     }

//     void update(int index, int val) {
//         int odd = (*nums)[index];
//         int diff = val - odd;
//         bit->add(index + 1, diff);
//         (*nums)[index] = val;
//     }

//     int sumRange(int left, int right) {
//         return bit->queryRange(left + 1, right + 1);
//     }
// };

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