差分专题的练习

神经，树状数组做多了一开始还想着用树状数组来查询差分数组，但是我们要进行所有元素的查询，直接过一遍就好啦

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        vector<int> c(105, 0);
        for (int i = 0; i < nums.size(); i++) {
            c[nums[i][0]] += 1;
            c[nums[i][1] + 1] -= 1;
        }
        int ans = 0; int num = 0;
        for (int i = 1; i < 105; i++) {
            num += c[i];
            ans += (num > 0);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

就好像这个题目，我们可以小试牛刀直接进行树状数组

int a[60];
int lowbit(int x) { return x & (-x); }
void add(int x, int p) {
    for (int i = x; i <= 50; i += lowbit(i)) {
        a[i] += p;
    }
}
int query(int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i)) {
        sum += a[i];
    }return sum;
}


class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        for (int i = 1; i <= 50; i++) a[i] = 0;
        for (int i = 0; i < ranges.size(); i++) {
            add(ranges[i][0], 1);
            add(ranges[i][1] + 1, -1);
        }
        int flag = 1;
        for (int i = left; i <= right; i++) {
            int t = query(i);
            if (!t) {
                flag = 0; break;
            }
        }return flag;
    }
};
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