LeetCode715. Range 模块

题目描述

本题目来自LeetCode上的『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 次

题解1 - 线段树

值域为 $[1, 1e9]$，选用『动态开点的懒标记线段树』，$val$ 定义为当前区间有多少个点被跟踪，懒标记 $add=1$ 表示跟踪，$add=-1$ 表示取消跟踪，需要将 $val$ 置零。
直接套板子（一开始用的c++直接TLE，原封不动换成java能够通过，懒得优化了…）

代码

class RangeModule {
    class Node {
        Node l, r;
        int val, add;
    }
    private int N = (int)1e9;
    private Node root = new Node();
    private void update(Node node, int lc, int rc, int l, int r, int v) {
        if (l > r) {
            return;
        }
        int len = rc - lc + 1;
        if (l <= lc && rc <= r) {
            node.val = v == 1 ? len : 0;
            node.add = v;
            return;
        }
        pushdown(node, len);
        int mid = lc + ((rc - lc) >> 1);
        if (l <= mid) {
            update(node.l, lc, mid, l, r, v);
        }
        if (r > mid) {
            update(node.r, mid + 1, rc, l, r, v);
        }
        pushup(node);
    }
    private int query(Node node, int lc, int rc, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l <= lc && rc <= r) return node.val;
        pushdown(node, rc - lc + 1);
        int mid = lc + ((rc - lc) >> 1); 
        int ans = 0;
        if (l <= mid) {
            ans = query(node.l, lc, mid, l, r);
        }
        if (r > mid) {
            ans += query(node.r, mid + 1, rc, l, r);
        }
        return ans;
    }
    private void pushdown(Node node, int len) {
        if (node.l == null) {
            node.l = new Node();
        }
        if (node.r == null) {
            node.r = new Node();
        }
        if (node.add == 0) {
            return;
        }
        int add = node.add;
        if (add == -1) {
            node.l.val = 0;
            node.r.val = 0;
        } else {
            node.l.val = len - len / 2;
            node.r.val = len / 2;
        }
        node.l.add = add;
        node.r.add = add;
        node.add = 0;
    }
    private void pushup(Node node) {
        node.val = node.l.val + node.r.val;
    }
    public void addRange(int left, int right) {
        update(root, 0, N, left, right - 1, 1);
    }
    public boolean queryRange(int left, int right) {
        return query(root, 0, N, left, right - 1) == right - left;
    }
    public void removeRange(int left, int right) {
        update(root, 0, N, left, right - 1, -1);
    }
}

复杂度分析

时间复杂度：addRange、queryRange 和 removeRange 操作复杂度均为 $O(\log{n})$
空间复杂度：$O(m\log{n})$

题解2 - 珂学

珂朵莉树（Chtholly Tree）源自 CF896C，又叫老司机树ODT(Old Driver Tree)
其实叫做『颜色段均摊』更合适，严格意义上说这并不能算是一种数据结构，常用于骗分。

代码

class RangeModule {
private:
    struct Node {
        int l, r;
        mutable int v;
        Node(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
        inline bool operator<(const Node &o) const { return l < o.l; }
    };
    set<Node> odt;
    const int n = 1e9;
    auto split(int x) {
        if (x > n) return odt.end();
        auto it = odt.lower_bound(Node{x, 0, 0});
        if (it != odt.end() && it->l == x) return it;
        --it;
        int l = it->l, r = it->r, v = it->v;
        odt.erase(it);
        odt.insert(Node(l, x - 1, v));
        return odt.insert(Node(x, r, v)).first;
    }
    void assign(int l, int r, int v) {
        auto itr = split(r + 1), itl = split(l);
        odt.erase(itl, itr);
        odt.insert(Node(l, r, v));    
    }
    int query(int l, int r) {
        auto itr = split(r + 1), itl = split(l);
        int res = 0;
        for (; itl != itr; ++itl) {
            res += (itl->r - itl->l + 1) * itl->v;
        }
        return res;
    }
public:
    RangeModule() {
        odt.insert(Node(0, n, 0));
    }
    
    void addRange(int left, int right) {
        assign(left, right - 1, 1);
    }
    
    bool queryRange(int left, int right) {
        return query(left, right - 1) == right - left;
    }
    
    void removeRange(int left, int right) {
        assign(left, right - 1, 0);
    }
};