LeetCode 面试题 10.10. 数字流的秩
题目描述
题意分析
设计一个数据结构，支持
track(x)把数字加入数据流，以及getRankOfNumber(x)返回当前流中小于等于x的元素个数。重复值要分别计数，不是只算不同数字的种类。题面只规定
x <= 50000，没有给出非负下界，不能直接把原值当作数组下标。本文按题目int接口采用 32 位有符号整数范围，Go 实现也采用同一输入范围；将整个可用值域平移到正的宽整数下标，再维护频次前缀和。树状数组下标必须从
1开始，因为lowbit(0) = 0会让更新无法前进。取偏移量OFFSET = 1 - Integer.MIN_VALUE，原值映射为index = x + OFFSET，使最小整数对应下标1，并保持数值的大小顺序。偏移量和下标用long/int64保存。
解法：树状数组维护频次前缀和
核心思路
[!blue]
把每个数值看成频次数组中的一个位置。
track(x)是对应位置加一，查询秩则是从最小值到x的频次总和，正好对应树状数组的单点更新和前缀查询。数值平移后顺序不变，所以查询到x + OFFSET仍然表示统计所有小于等于x的元素。
c[i]保存下标区间[i - lowbit(i) + 1, i]的频次和。更新位置i时，通过i += lowbit(i)向上跳到包含它的父区间，把沿途计数都加一。查询时先取出当前末尾区间，再令i -= lowbit(i)移到剩余前缀的末端；这些区间互不重叠，合起来恰好覆盖所求前缀。平移后的下标范围很大，不能实际分配整张数组。改用哈希表保存被更新过的树状数组节点，没有保存的节点就视为计数零。每次插入只会涉及对数个父区间，查询也只读取对数个末尾区间，所以稀疏存储保留了树状数组的操作方式，同时避免按整个值域分配空间。
每个区间计数始终等于已插入数字在该区间中的总频次。查询区间包含
x自身对应的位置，所以重复插入的等值数字都会分别计入；尚未插入任何数字时，所有读取值都是零，查询自然返回零。
解题步骤
- 设置下标上界
50000 + OFFSET，用空哈希表初始化稀疏树状数组。track(x)调用update(x + OFFSET, 1)，重复插入仍然累加。update从当前下标向上跳父节点，把沿途区间和都加一。getRankOfNumber(x)调用query(x + OFFSET)，逐块累加所求前缀。更新下标始终为正并严格增大，超过上界时结束；查询每次清除最低的一个置位，到零时结束。负数、零和上界值都使用同一套映射与查询规则，计数结果最多是插入次数，仍用普通整数保存。
代码实现
// 稀疏树状数组支持单点增加和频次前缀和查询。
class BinaryIndexedTree {
private long n;
private Map<Long, Integer> c;
public BinaryIndexedTree(long n) {
this.n = n;
this.c = new HashMap<>();
}
public void update(long x, int delta) {
for (; x <= n; x += x & -x) {
c.put(x, c.getOrDefault(x, 0) + delta);
}
}
public int query(long x) {
int s = 0;
for (; x > 0; x -= x & -x) {
s += c.getOrDefault(x, 0);
}
return s;
}
}
class StreamRank {
private static final long OFFSET = 1L - Integer.MIN_VALUE;
private BinaryIndexedTree tree = new BinaryIndexedTree(50000L + OFFSET);
public StreamRank() {}
public void track(int x) {
tree.update((long) x + OFFSET, 1);
}
public int getRankOfNumber(int x) {
return tree.query((long) x + OFFSET);
}
}
// 稀疏树状数组支持单点增加和频次前缀和查询。
type BinaryIndexedTree struct {
n int64
c map[int64]int
}
func NewBinaryIndexedTree(n int64) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, c: make(map[int64]int)}
}
func (bit *BinaryIndexedTree) update(x int64, delta int) {
for ; x <= bit.n; x += x & -x {
bit.c[x] += delta
}
}
func (bit *BinaryIndexedTree) query(x int64) int {
s := 0
for ; x > 0; x -= x & -x {
s += bit.c[x]
}
return s
}
type StreamRank struct {
tree *BinaryIndexedTree
}
const rankOffset int64 = (1 << 31) + 1
func Constructor() StreamRank {
return StreamRank{NewBinaryIndexedTree(50000 + rankOffset)}
}
func (this *StreamRank) Track(x int) {
this.tree.update(int64(x)+rankOffset, 1)
}
func (this *StreamRank) GetRankOfNumber(x int) int {
return this.tree.query(int64(x) + rankOffset)
}
复杂度分析
- 时间复杂度：构造为 $O(1)$。设映射后的下标上界为
U，一次插入或查询访问 $O(\log U)$ 个节点；哈希表操作按期望常数时间计，单次操作为期望 $O(\log U)$。本实现的U = 50000 - Integer.MIN_VALUE + 1。- 空间复杂度：$O(q\log U)$ 的上界，
q是已插入次数，每次至多新增对数个节点；已有节点会复用，查询不增加存储。
关键点总结
[!green]
- “秩 = 小于等于某值的数量”就是频次数组的前缀和；动态单点插入 + 前缀查询优先考虑树状数组。
- 统一平移保持数值顺序，并让最小整数落在有效下标
1；偏移和下标都要使用宽整数。- 稀疏表只保存被更新的区间，不需要为整个整数范围分配数组。
- 若改成统计严格小于
x，应查询x + OFFSET - 1；等号直接体现在前缀右端点上。
易错点总结
[!yellow]
- 假定输入非负并只加一：题面未给出该下界，负数可能被映射到零或负下标，更新无法正确进行。
- 在普通整数中计算偏移量：
1 - Integer.MIN_VALUE会超出 32 位范围，应先使用宽整数再运算。- 把频次写成一而不是累加：重复插入会被覆盖，秩应按出现次数统计。
- 插入与查询使用不同的映射：查询前缀将不再对应原值中小于等于
x的范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 307. 区域和检索 - 数组可修改 | 中等 | 同样维护单点变化和前缀区间和，本题下标表示数值、单点值表示出现频次。 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 同样通过频次前缀和求秩，原题倒序扫描数组统计右侧更小值。 |