题目描述
这是 LeetCode 上的 933. 最近的请求次数 ，难度为 简单。
Tag : 「线段树」、「分块」
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 00 。int ping(int t)在时间 tt 添加一个新请求，其中 tt 表示以毫秒为单位的某个时间，并返回过去 30003000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t][t−3000,t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 tt 值。
示例 1：
输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 解释： RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1 recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2 recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3 复制代码
提示：
- 1 <= t <= 10^91<=t<=109
- 保证每次对
ping调用所使用的 tt 值都 严格递增 - 至多调用
ping方法 10^4104 次
以下内容（支持任意的 [l, r][l,r] 查询）基于我漏看了 tt 递增这一条件。由于 tt 递增，因此往前距离大于 30003000 的记录无须保留，从而简化了问题，可以使用队列直接做，今天打字很多了，不补充了。
基本分析
根据题意，题目涉及「单点修改」和「区间查询」，根据 区间求和问题 的总结，可以使用「树状数组」和「线段树」进行求解。
但是留意到 tt 的数据范围为 1e91e9，虽然调用次数是 1e41e4，但由于本题是「强制在线」问题，因此我们无法利用「离散化」手段来解决 MLE 问题，而要使用「线段树（动态开点）」来解决。
线段树（动态开点）
动态开点的优势在于，不需要事前构造空树，而是在插入操作 update 和查询操作 query 时根据访问需要进行「开点」操作。由于我们不保证查询和插入都是连续的，因此对于父节点 uu 而言，我们不能通过 u << 1 和 u << 1 | 1 的固定方式进行访问，而要将节点 tr[u]tr[u] 的左右节点所在 tr 数组的下标进行存储，分别记为 ls 和 rs 属性。对于 tr[u].ls = 0tr[u].ls=0 和 tr[u].rs = 0tr[u].rs=0 则是代表子节点尚未被创建，当需要访问到它们，而又尚未创建的时候，则将其进行创建。
线段树的插入和查询都是 \log{n}logn 的（如果涉及区间修改，则由懒标记来确保 \log{n}logn 复杂度），因此我们在单次操作的时候，最多会创建数量级为 \log{n}logn 的点，因此空间复杂度为 O(m\log{n})O(mlogn)，而不是 O(4 * n)O(4∗n)，而开点数的预估需不能仅仅根据 \log{n}logn 来进行，还要对具体常数进行分析，才能得到准确的点数上界。
动态开点相比于原始的线段树实现，本质仍是使用「满二叉树」的形式进行存储，只不过是按需创建区间，如果我们是按照连续段进行查询或插入，最坏情况下仍然会占到 4 * n4∗n 的空间，因此盲猜 \log{n}logn 的常数在 44 左右，保守一点可以直接估算到 66，因此我们可以估算点数为 6 * m * \log{n}6∗m∗logn，其中 n = 1e9n=1e9 和 m = 1e4m=1e4 分别代表值域大小和查询次数。
当然一个比较实用的估点方式可以「尽可能的多开点数」，利用题目给定的空间上界和我们创建的自定义类（结构体）的大小，尽可能的多开（ Java 的 128M128M 可以开到 5 * 10^65∗106 以上）。
代码：
class RecentCounter { class Node { // ls 和 rs 分别代表当前节点（区间）的左右子节点在 tr 的下标 // val 代表在当前节点（区间）所包含的数的个数 int ls, rs, val; } int N = (int)1e9, M = 800010, idx = 1; Node[] tr = new Node[M]; void update(int u, int lc, int rc, int x, int v) { if (lc == x && rc == x) { tr[u].val += (rc - lc + 1) * v; return ; } lazyCreate(u); int mid = lc + rc >> 1; if (x <= mid) update(tr[u].ls, lc, mid, x, v); else update(tr[u].rs, mid + 1, rc, x, v); pushup(u); } int query(int u, int lc, int rc, int l, int r) { if (l <= lc && rc <= r) return tr[u].val; lazyCreate(u); 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 lazyCreate(int u) { if (tr[u] == null) tr[u] = new Node(); if (tr[u].ls == 0) { tr[u].ls = ++idx; tr[tr[u].ls] = new Node(); } if (tr[u].rs == 0) { tr[u].rs = ++idx; tr[tr[u].rs] = new Node(); } } void pushup(int u) { tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val; } public int ping(int t) { update(1, 1, N, t, 1); return query(1, 1, N, Math.max(0, t - 3000), t); } } 复制代码
- 时间复杂度：令
ping的调用次数为 mm，值域大小为 nn，线段树的插入和查询复杂度均为 O(\log{n})O(logn) - 空间复杂度：O(m * \log{n})O(m∗logn)
分块
另外一个稍有遗憾的算法是「分块」。
通常来说，值域范围为 n = 1e9n=1e9，我们可以定义块大小为 \sqrt{n}n，这样时空复杂度都是 O(\sqrt{n})O(n)。
回到本题，我们定义一个 region 数组，用于存储每个块所包含的数的个数。
对于在位置 xx 插入一个值 vv 而言，我们可以计算位置 xx 所在的块编号 idx = \left \lfloor \frac{x}{m} \right \rflooridx=⌊mx⌋，然后对块大小进行累加操作（region[idx] += xregion[idx]+=x）。同时由于在查询 [t - 3000, t][t−3000,t] 时不总是覆盖完整的块（也就是我们可能需要询问某一段的总个数，而这一段仅是块内的部分区间），因此我们需要额外记录位置 xx 当前所包含的总数是多少，本题值域大小达到了 1e91e9，因此不能使用静态数组来做，只能使用哈希表来实现动态记录。
我们可以分析单个 ping 操作的计算量/复杂度：
update操作：O(1)O(1)；query操作：不限制区域大小的话，计算量为 1e5 * C1e5∗C（CC 是一个小于 44 的常数），由于存在 [t - 3000, t][t−3000,t] 的限制，相当于这部分操作全部变成块内了，计算量固定为 30003000。
于是有通过了所有样例，居然还 TLE 的结果？？？（这是啥测评机制
但经过分析，我们知道瓶颈在于块内操作过多，我们可以利用 [t - 3000, t][t−3000,t] 来优化我们的分块算法：直接定义块大小为 300300，然后倒推出需要多个块空间，分块算法就可以过了（特别说明：通过时间为 我不信，卡不掉 🤣2022-05-06，未来可能还会有无聊的人来卡分块。
代码：
class RecentCounter { static int m = 300, n = (int)(1e9 / m) + 10; static Map<Integer, Integer> map = new HashMap<>(); static int[] region = new int[n]; int getIdx(int x) { return x / m; } void update(int x, int v) { map.put(x, map.getOrDefault(x, 0) + v); region[getIdx(x)] += v; } int query(int l, int r) { int ans = 0; if (getIdx(l) == getIdx(r)) { for (int k = l; k <= r; k++) ans += map.getOrDefault(k, 0); } else { int i = l, j = r; while (getIdx(i) == getIdx(l)) ans += map.getOrDefault(i++, 0); while (getIdx(j) == getIdx(r)) ans += map.getOrDefault(j--, 0); for (int k = getIdx(i); k <= getIdx(j); k++) ans += region[k]; } return ans; } public RecentCounter() { map.clear(); Arrays.fill(region, 0); } public int ping(int t) { update(t, 1); return query(Math.max(0, t - 3000), t); } } 复制代码
- 时间复杂度：通常情况下：调用次数为 mm，值域大小为 nn，复杂度为 O(\sqrt{n})O(n)；本题：O(C)O(C)，其中 C = 300C=300 为块大小
- 空间复杂度：通常情况下：O(m +\sqrt{n})O(m+n)；本题：O(m + M)O(m+M)，其中 MM 为分块数组大小
最后
这是我们「刷穿 LeetCode」系列文章的第 No.933 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
