715. Range 模块

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

实现 RangeModule 类:

  • RangeModule() 初始化数据结构的对象。
  • void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
  • boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
  • void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）

提示：

  • 1 <= left < right <= 10^9
  • 在单个测试用例中，对 addRange 、 queryRange 和 removeRange 的调用总数不超过 10^4 次

结点指针法动态线段树

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
class RangeModule {
    class Node {
        Node l, r;
        int val, lazy;
    }
    Node root = new Node();
    void pushDown(Node cur, int len) {
        if (cur.l == null) cur.l = new Node();
        if (cur.r == null) cur.r = new Node();
        if (cur.lazy == 0) return;
        else if (cur.lazy == 1) {
            cur.l.val = (len - len/2);
            cur.r.val = len/2;
        }
        else if (cur.lazy == -1) {
            cur.l.val = 0;
            cur.r.val = 0;
        }
        cur.l.lazy = cur.lazy;
        cur.r.lazy = cur.lazy;
        cur.lazy = 0;
    }
    void pushUp(Node cur) {
        cur.val = cur.l.val + cur.r.val;
    }
    void upd(Node cur, int l, int r, int tl, int tr, int val) {
        if (tl <= l && r <= tr) {
            cur.val = val == 1 ? r - l + 1 : 0;
            cur.lazy = val;
        }
        else {
            pushDown(cur, r-l+1);
            int m = l + (r-l)/2;
            if (tl <= m) upd(cur.l, l, m, tl, tr, val);
            if (m+1 <= tr) upd(cur.r, m+1, r, tl, tr, val);
            pushUp(cur);
        }
    }
    int query(Node cur, int l, int r, int tl, int tr) {
        if (tl <= l && r <= tr) {
            return cur.val;
        }
        else {
            pushDown(cur, r-l+1);
            int m = l + (r-l)/2, ans = 0;
            if (tl <= m) ans += query(cur.l, l, m, tl, tr);
            if (m+1 <= tr) ans += query(cur.r, m+1, r, tl, tr);
            pushUp(cur);
            return ans;
        }
    }
    public RangeModule() {

    }
    int L = 1, R = (int)1e9;
    public void addRange(int left, int right) {
        upd(root, L, R, left, right-1, 1);
    }
    
    public boolean queryRange(int left, int right) {
        return query(root, L, R, left, right-1) == right - left;
    }
    
    public void removeRange(int left, int right) {
        upd(root, L, R, left, right-1, -1);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */