【区间和专题の前缀和】线段树（动态开点）运用题

题目描述

这是 LeetCode 上的「732. 我的日程安排表 III」，难度为「困难」。

Tag : 「线段树（动态开点）」、「分块」、「线段树」

当

k

个日程安排有一些时间上的交叉时（例如

k

个日程安排都在同一时间内），就会产生

k

次预订。

给你一些日程安排

[start, end)

，请你在每个日程安排添加后，返回一个整数

k

，表示所有先前日程安排会产生的最大

k

次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int start, int end) 返回一个整数

k

，表示日历中存在的

k

次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

复制

提示：

0 <= start < end <= 10^9

• 每个测试用例，调用 book 函数最多不超过

400

次

线段树（动态开点）

和 731. 我的日程安排表 II 几乎完全一致，只需要将对「线段树」所维护的节点信息进行调整即可。

线段树维护的节点信息包括：

• ls/rs: 分别代表当前节点的左右子节点在线段树数组 tr 中的下标；
• add: 懒标记；
• max: 为当前区间的最大值。

对于常规的线段树实现来说，都是一开始就调用 build 操作创建空树，而线段树一般以「满二叉树」的形式用数组存储，因此需要

4 \times n

的空间，并且这些空间在起始 build 空树的时候已经锁死。

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

但对于本题而言，由于「强制在线」的原因，我们无法进行「离散化」，同时值域大小达到

1e9

级别，因此如果我们想要使用「线段树」进行求解，只能采取「动态开点」的方式进行。

动态开点的优势在于，不需要事前构造空树，而是在插入操作 add 和查询操作 query 时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的，因此对于父节点

u

而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，而要将节点

tr[u]

的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。对于

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 = 1e3

分别代表值域大小和查询次数。

当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 128M 可以开到

5 \times 10^6

以上）。

代码：

class MyCalendarThree {
    class Node {
        int ls, rs, add, max;
    }
    int N = (int)1e9, M = 4 * 400 * 20, cnt = 1;
    Node[] tr = new Node[M];
    void update(int u, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            tr[u].add += v;
            tr[u].max += v;
            return ;
        }
        lazyCreate(u);
        pushdown(u);
        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].max;
        lazyCreate(u);
        pushdown(u);
        int mid = lc + rc >> 1, ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans = Math.max(ans, query(tr[u].rs, mid + 1, rc, l, r));
        return ans;
    }
    void lazyCreate(int u) {
        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();
        }
    }
    void pushdown(int u) {
        tr[tr[u].ls].add += tr[u].add; tr[tr[u].rs].add += tr[u].add;
        tr[tr[u].ls].max += tr[u].add; tr[tr[u].rs].max += tr[u].add;
        tr[u].add = 0;
    }
    void pushup(int u) {
        tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
    }
    public int book(int start, int end) {
        update(1, 1, N + 1, start + 1, end, 1);
        return query(1, 1, N + 1, 1, N + 1);
    }
}

复制

• 时间复杂度：令

n

为值域大小，本题固定为

1e9

，线段树的查询和增加复杂度均为

O(\log{n})

• 空间复杂度：令询问数量为

m

，复杂度为

O(m\log{n})

带懒标记的分块（TLE）

实际上，还存在另外一种十分值得学习的算法：分块。

但该做法被奇怪的测评机制卡掉，是给每个样例都定了执行用时吗 ？

旧题解没有这种做法，今天补充的，我们可以大概讲讲「分块」算法是如何解决涉及「区间修改」，也就是带懒标记的问题。

对于本题，我们设定两个块数组 max 和 add，其中 max[idx] 含义为块编号为 idx 的连续区间的最大重复值，而 add[idx] 代表块编号的懒标记，同时使用「哈希表」记录下某些具体位置的覆盖次数。

然后我们考虑如何指定块大小，设定一个合理的块大小是减少运算量的关键。

通常情况下，我们会设定块大小为

\sqrt{n}

，从而确保块内最多不超过

\sqrt{n}

个元素，同时块的总个数也不超过

\sqrt{n}

，即无论我们是块内暴力，还是操作多个块，复杂度均为

O(\sqrt{n})

。因此对于本题而言，设定块大小为

\sqrt{1e9}

（经试验，调成

1200010

能够通过较多样例），较为合适。

对于涉及「区间修改」的分块算法，我们需要在每次修改和查询前，先将懒标记下传到区间的每个元素中。

然后考虑如何处理「块内」和「块间」操作：

• 块内操作：
  • 块内更新：直接操作 map 进行累加，同时使用更新后的 map 来维护相应的 max[idx]；
  • 块内查询：直接查询 map 即可；
• 块间操作：
  • 块间更新：直接更新懒标记 add[idx] 即可，同时由于我们是对整个区间进行累加操作，因此最大值必然也会同步被累加，因此同步更新 max[idx]；
  • 块间查询：直接查询 max[idx] 即可。

代码：

class MyCalendarThree {
    static int N = (int)1e9 + 10, M = 1200010, SZ = N / M + 10;
    static int[] max = new int[M], add = new int[M];
    static Map<Integer, Integer> map = new HashMap<>();
    int minv = -1, maxv = -1;
    int getIdx(int x) {
        return x / SZ;
    }
    void add(int l, int r) {
        pushdown(l); pushdown(r);
        if (getIdx(l) == getIdx(r)) {
            for (int k = l; k <= r; k++) {
                map.put(k, map.getOrDefault(k, 0) + 1);
                max[getIdx(k)] = Math.max(max[getIdx(k)], map.get(k));
            }
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) {
                map.put(i, map.getOrDefault(i, 0) + 1);
                max[getIdx(i)] = Math.max(max[getIdx(i)], map.get(i));
                i++;
            }
            while (getIdx(j) == getIdx(r)) {
                map.put(j, map.getOrDefault(j, 0) + 1);
                max[getIdx(j)] = Math.max(max[getIdx(j)], map.get(j));
                j--;
            }
            for (int k = getIdx(i); k <= getIdx(j); k++) {
                max[k]++; add[k]++;
            }
        }
    }
    int query(int l, int r) {
        pushdown(l); pushdown(r);
        int ans = 0;
        if (getIdx(l) == getIdx(r)) {
            for (int k = l; k <= r; k++) ans = Math.max(ans, map.getOrDefault(k, 0));
        } else {
            int i = l, j = r;
            while (getIdx(i) == getIdx(l)) ans = Math.max(ans, map.getOrDefault(i++, 0));
            while (getIdx(j) == getIdx(r)) ans = Math.max(ans, map.getOrDefault(j--, 0));
            for (int k = getIdx(i); k <= getIdx(j); k++) ans = Math.max(ans, max[k]);
        }
        return ans;
    }
    void pushdown(int x) {
        int idx = getIdx(x);
        if (add[idx] == 0) return ;
        int i = x, j = x + 1;
        while (getIdx(i) == idx) map.put(i, map.getOrDefault(i--, 0) + add[idx]);
        while (getIdx(j) == idx) map.put(j, map.getOrDefault(j++, 0) + add[idx]);
        add[idx] = 0;
    }
    public MyCalendarThree() {
        Arrays.fill(max, 0);
        Arrays.fill(add, 0);
        map.clear();
    }
    public int book(int start, int end) {
        add(start + 1, end);
        minv = minv == -1 ? start : Math.min(minv, start);
        maxv = maxv == -1 ? end + 1 : Math.max(maxv, end + 1);
        return query(minv, maxv);
    }
}

复制

• 时间复杂度：令

M

为块大小，复杂度为

O(\sqrt{M})

• 空间复杂度：

O(C \times \sqrt{M})

，其中

C = 1e3

为最大调用次数

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。