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：

输入
[“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 次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/range-module
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

借这个题进一步学习了一下线段树，下面写法是基于链表的动态开点写法，支持区间修改。

本题基本就是套一个模板，主要需要修改的地方如下：

判断一个区间的数是否都被跟踪可以通过比较「区间和」与「区间长度」来判断。因此，无论对一个数反复add几次，其对应的值都为1，这样才可以基于比较区间和与区间长度来判断一个区间的数是否都被跟踪。

代码

class RangeModule {
    public RangeModule() {
    }
    public void addRange(int left, int right) {
        update(root, 1, N, left, right - 1, 1);
    }
    public boolean queryRange(int left, int right) {
        return query(root, 1, N, left, right - 1) == right - left;
    }
    public void removeRange(int left, int right) {
        update(root, 1, N, left, right - 1, -1);
    }
    class Node {
        Node left, right;
        // node.val表示node对应区间的区间和
        int val, add;
    }
    private int N = (int) 1e9;
    private Node root = new Node();
    // 参数val表示是否被跟踪，1被跟踪，-1没有被跟踪
    public void update(Node node, int l, int r, int dataL, int dataR, int val) {
        if (dataL <= l && r <= dataR) {
            node.val = val == 1 ? r - l + 1 : 0;
            node.add = val;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(node, mid - l + 1, r - mid);
        if (dataL <= mid) update(node.left, l, mid, dataL, dataR, val);
        if (dataR > mid) update(node.right, mid + 1, r, dataL, dataR, val);
        pushUp(node);
    }
    public int query(Node node, int l, int r, int dataL, int dataR) {
        if (dataL <= l && r <= dataR) return node.val;
        int mid = (l + r) >> 1;
        pushDown(node, mid - l + 1, r - mid);
        int ans = 0;
        if (dataL <= mid) ans += query(node.left, l, mid, dataL, dataR);
        if (dataR > mid) ans += query(node.right, mid + 1, r, dataL, dataR);
        return ans;
    }
    private void pushUp(Node node) {
        node.val = node.left.val + node.right.val;
    }
    private void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return;
        node.left.val = node.add == 1 ? leftNum : 0;
        node.right.val = node.add == 1 ? rightNum : 0;
        node.left.add = node.add;
        node.right.add = node.add;
        node.add = 0;
    }
}