LC 1109. 航班预订统计

题目描述

这是 LeetCode 上的 1109. 航班预订统计 ，难度为中等。

这里有 $n$ 个航班，它们分别从 $1$ 到 $n$ 进行编号。

有一份航班预订表 bookings，表中第 $i$ 条预订记录 $bookings[i] = [first_i, last_i, seats_i]$ 意味着在从 $first_i$ 到 $last_i$ （包含 $first_i$ 和 $last_i$ ）的 每个航班 上预订了 $seats_i$ 个座位。

请你返回一个长度为 $n$ 的数组 answer，其中 $answer[i]$ 是航班 $i$ 上预订的座位总数。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

输出：[10,55,45,25,25]

解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：
1
2
3
4
5
6
7
8
9
10
输入：bookings = [[1,2,10],[2,2,15]], n = 2

输出：[10,25]

解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

  • $1 <= n <= 2 * 10^4$
  • $1 <= bookings.length <= 2 * 10^4$
  • $bookings[i].length == 3$
  • $1 <= first_i <= last_i <= n$
  • $1 <= seats_i <= 10^4$

基本分析

本题只涉及「区间修改 + 单点查询」，属于「区间求和」问题中的入门难度。

对于各类「区间求和」问题，该用什么方式进行求解，之前在 这里 提到过。

此处可以再总结一下（加粗字体为最佳方案）：

  • 数组不变，区间查询：前缀和、树状数组、线段树；
  • 数组单点修改，区间查询：树状数组、线段树；
  • 数组区间修改，单点查询：差分、线段树；
  • 数组区间修改，区间查询：线段树。

注意：上述总结是对于一般性而言的（能直接解决的），对标的是模板问题。
但存在经过一些经过“额外”操作，对问题进行转化，从而使用别的解决方案求解的情况。
例如某些问题，我们可以先对原数组进行差分，然后使用树状数组，也能解决区间修改问题。
或者使用多个树状数组来维护多个指标，从而实现类似线段树的持久化标记操作。
但这些不属于一般性，所以就不添加到题解了。

差分

本题只涉及「区间修改 + 单点查询」，因此是一道「差分」的模板题。

「差分」可以看做是求「前缀和」的逆向过程。

对于一个「将区间 $[l, r]$ 整体增加一个值 $v$」操作，我们可以对差分数组 $c$ 的影响看成两部分：

  • 对 $c[l] += v$：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于 $l$ 的位置都增加了值 $v$；
  • 对 $c[r + 1] -= v$：由于我们期望只对 $[l, r]$ 产生影响，因此需要对下标大于 $r$ 的位置进行减值操作，从而抵消“影响”。

对于最后的构造答案，可看做是对每个下标做“单点查询”操作，只需要对差分数组求前缀和即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] corpFlightBookings(int[][] bs, int n) {
        int[] c = new int[n + 1];
        for (int[] bo : bs) {
            int l = bo[0] - 1, r = bo[1] - 1, v = bo[2];
            c[l] += v;
            c[r + 1] -= v;
        }
        int[] ans = new int[n];
        ans[0] = c[0];
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] + c[i];
        }
        return ans;
    }
}

  • 时间复杂度：令 bs 长度为 $m$，预处理差分数组的复杂度为 $O(m)$；构造答案复杂度为 $O(n)$。整体复杂度为 $O(m + n)$
  • 空间复杂度：$O(n)$

线段树

在「基本分析」中，我们发现几乎所有的「区间求和」问题都可以使用线段树解决。

那么是否无脑写线段树呢？答案并不是，恰好相反。

线段树代码很长，且常数很大，实际表现不算很好。只有不得不写「线段树」的时候，我们才考虑线段树。

回到本题，由于涉及「区间修改」操作，因此我们需要对线段树进行持久化标记（懒标记），从而确保操作仍为 $\log$ 级别的复杂度。

代码：

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
class Solution {
    class Node {
        int l, r, v, add;
        Node(int _l, int _r) {
            l = _l; r = _r;
        }
    }
    int N = 20009;
    Node[] tr = new Node[N * 4];
    void pushup(int u) {
        tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
    }
    void pushdown(int u) {
        int add = tr[u].add;
        tr[u << 1].v += add;
        tr[u << 1].add += add;
        tr[u << 1 | 1].v += add;
        tr[u << 1 | 1].add += add;
        tr[u].add = 0;
    }
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l != r) {
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
        }
    }
    void update(int u, int l, int r, int v) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].v += v;
            tr[u].add += v;
        } else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) update(u << 1, l, r, v);
            if (r > mid) update(u << 1 | 1, l, r, v);
            pushup(u);
        }
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u].v;
        } else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            int ans = 0;
            if (l <= mid) ans += query(u << 1, l, r);
            if (r > mid) ans += query(u << 1 | 1, l, r);
            return ans;
        }
    }
    public int[] corpFlightBookings(int[][] bs, int n) {
        build(1, 1, n);
        for (int[] bo : bs) {
            update(1, bo[0], bo[1], bo[2]);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = query(1, i + 1, i + 1);
        }
        return ans;
    }
}

  • 时间复杂度：线段树建树复杂度为 $O(n)$，其余操作复杂度为 $O(\log{n})$。对于本题，令 bs 长度为 $m$，整体复杂度为 $O(m\log{n} + n\log{n})$
  • 空间复杂度：$O(n)$

最后

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

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

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

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