乐趣区

关于程序员:宫水三叶的刷题日记715-Range-模块

题目形容

这是 LeetCode 上的 715. Range 模块 ,难度为 艰难

Tag :「线段树」、「线段树(动静开点)」

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$
  • 在单个测试用例中,对 addRangequeryRange 和 removeRange 的调用总数不超过 $10^4$ 次

根本剖析

令 $m$ 为 addRangequeryRangeremoveRange 的调用总数,$n = 1e9$ 为值域大小。

因为值域过大,咱们无奈间接应用空间大小固定为 $4 \times n$ 的惯例线段树,而要采纳「动静开点」的形式,其中动静开点的形式有两种 :「须要进行估点的数组实现」和「毋庸估点的动静指针」。

设计 Node 节点保护什么信息:

  • lsrs 别离指向左右区间子节点(当采纳「估点数组」形式时,记录的是左右区间子节点在线段树数组中的下标;在「动静指针」形式时,记录的是左右区间子节点对象);
  • sum 为记录以后区间有多少个整数被追踪;
  • add 为懒标记,当 add = -1 代表 removeRange 懒标记,当 add = 1 则代表 addRange 懒标记。

线段树(动静开点)- 数组估点

对于惯例的线段树实现来说,都是一开始就调用 build 操作创立空树,而线段树个别以「满二叉树」的模式用数组存储,因而须要 $4 \times n$ 的空间,并且这些空间在起始 build 空树的时候曾经锁死。

如果一道题仅仅是「值域很大」的离线题(提前通晓所有的询问),咱们还能通过「离散化」来进行解决,将值域映射到一个小空间去,从而解决 MLE 问题。

但对于本题而言,因为「强制在线」的起因,咱们无奈进行「离散化」,同时值域大小达到 $1e9$ 级别,因而如果咱们想要应用「线段树」进行求解,只能采取「动静开点」的形式进行。

动静开点的劣势在于,不须要事先结构空树,而是在插入操作 add 和查问操作 query 时依据拜访须要进行「开点」操作。因为咱们不保障查问和插入都是间断的,因而对于父节点 $u$ 而言,咱们不能通过 u << 1u << 1 | 1 的固定形式进行拜访,而要将节点 $tr[u]$ 的左右节点所在 tr 数组的下标进行存储,别离记为 lsrs 属性。对于 $tr[u].ls = 0$ 和 $tr[u].rs = 0$ 则是代表子节点尚未被创立,当须要拜访到它们,而又尚未创立的时候,则将其进行创立。

因为存在「懒标记」,线段树的插入和查问都是 $\log{n}$ 的,因而咱们在单次操作的时候,最多会创立数量级为 $\log{n}$ 的点,因而空间复杂度为 $O(m\log{n})$,而不是 $O(4 \times n)$,而开点数的预估需不能仅仅依据 $\log{n}$ 来进行,还要对常熟进行剖析,能力失去精确的点数上界。

动静开点相比于原始的线段树实现,实质仍是应用「满二叉树」的模式进行存储,只不过是按需创立区间,如果咱们是依照间断段进行查问或插入,最坏状况下依然会占到 $4 \times n$ 的空间,因而盲猜 $\log{n}$ 的常数在 $4$ 左右,激进一点能够间接估算到 $6$,因而咱们能够估算点数为 $6 \times m \times \log{n}$,其中 $n = 1e9$ 和 $m = 1e4$ 别离代表值域大小和查问次数。

当然一个比拟实用的估点形式能够「尽可能的多开点数」,利用题目给定的空间上界和咱们创立的自定义类(构造体)的大小,尽可能的多开(Java128M 能够开到 $5 \times 10^6$ 以上)。

代码:

class RangeModule {
    class Node {int ls, rs, sum, add;}
    int N = (int)1e9 + 10, M = 500010, cnt = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int l, int r, int v) {
        int len = rc - lc + 1;
        if (l <= lc && rc <= r) {tr[u].sum = v == 1 ? len : 0;
            tr[u].add = v;
            return ;
        }
        pushdown(u, len);
        int mid = lc + rc >> 1;
        if (l <= mid) update(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    int query(int u, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return tr[u].sum;
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
        return ans;
    }
    void pushdown(int u, int len) {if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {tr[u].ls = ++cnt;
            tr[tr[u].ls] = new Node();}
        if (tr[u].rs == 0) {tr[u].rs = ++cnt;
            tr[tr[u].rs] = new Node();}
        if (tr[u].add == 0) return;
        if (tr[u].add == -1) {tr[tr[u].ls].sum = tr[tr[u].rs].sum = 0;
        } else {tr[tr[u].ls].sum = len - len / 2;
            tr[tr[u].rs].sum = len / 2;
        }
        tr[tr[u].ls].add = tr[tr[u].rs].add = tr[u].add;
        tr[u].add = 0;
    }
    void pushup(int u) {tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
    }
    public void addRange(int left, int right) {update(1, 1, N - 1, left, right - 1, 1);
    }
    public boolean queryRange(int left, int right) {return query(1, 1, N - 1, left, right - 1) == right - left;
    }
    public void removeRange(int left, int right) {update(1, 1, N - 1, left, right - 1, -1);
    }
}
  • 工夫复杂度:addRangequeryRangeremoveRange 操作复杂度均为 $O(\log{n})$
  • 空间复杂度:$O(m\log{n})$

线段树(动静开点)- 动静指针

利用「动静指针」实现的「动静开点」能够无效防止数组估点问题,更重要的是能够无效防止 new 大数组的初始化开销,对于 LC 这种还跟你算所有样例总时长的 OJ 来说,在不思考 static 优化 / 全局数组优化 的状况下,动静指针的形式要比估点的形式来得好。

代码:

class RangeModule {
    class Node {
        Node ls, rs;
        int sum, add;
    }
    int N = (int)1e9 + 10;
    Node root = new Node();
    void update(Node node, int lc, int rc, int l, int r, int v) {
        int len = rc - lc + 1;
        if (l <= lc && rc <= r) {
            node.sum = v == 1 ? len : 0;
            node.add = v;
            return ;
        }
        pushdown(node, len);
        int mid = lc + rc >> 1;
        if (l <= mid) update(node.ls, lc, mid, l, r, v);
        if (r > mid) update(node.rs, mid + 1, rc, l, r, v);
        pushup(node);
    }
    int query(Node node, int lc, int rc, int l, int r) {if (l <= lc && rc <= r) return node.sum;
        pushdown(node, rc - lc + 1);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(node.ls, lc, mid, l, r);
        if (r > mid) ans += query(node.rs, mid + 1, rc, l, r);
        return ans;
    }
    void pushdown(Node node, int len) {if (node.ls == null) node.ls = new Node();
        if (node.rs == null) node.rs = new Node();
        if (node.add == 0) return ;
        int add = node.add;
        if (add == -1) {node.ls.sum = node.rs.sum = 0;} else {
            node.ls.sum = len - len / 2;
            node.rs.sum = len / 2;
        }
        node.ls.add = node.rs.add = add;
        node.add = 0;
    }
    void pushup(Node node) {node.sum = node.ls.sum + node.rs.sum;}
    public void addRange(int left, int right) {update(root, 1, N - 1, left, right - 1, 1);
    }
    public boolean queryRange(int left, int right) {return query(root, 1, N - 1, left, right - 1) == right - left;
    }
    public void removeRange(int left, int right) {update(root, 1, N - 1, left, right - 1, -1);
    }
}
  • 工夫复杂度:addRangequeryRangeremoveRange 操作复杂度均为 $O(\log{n})$
  • 空间复杂度:$O(m\log{n})$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.715 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布

退出移动版