LeetCode 面试题 10.10. 数字流的秩

2026-03-28 HGNULB 约 5 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 面试题 10.10. 数字流的秩

题意分析

设计一个数据结构，支持 track(x) 把数字加入数据流，以及 getRankOfNumber(x) 返回当前流中小于等于 x 的元素个数。重复值要分别计数，不是只算不同数字的种类。

若每次查询都扫描全部历史数据，单次是 $O(n)$；维护有序数组可以二分查询，但中间插入仍是 $O(n)$。题目给出值域 0..50000，这是用频次数组上的前缀和数据结构换取对数操作的明确信号。

树状数组下标必须从 1 开始，因为更新依赖 lowbit(x) = x & -x；若从 0 开始，lowbit(0) = 0 会让更新死循环。所以原值 x 统一映射到下标 x + 1。

解法：树状数组维护频次前缀和

核心思路

把每个数值看成频次数组中的一个位置。track(x) 是单点加一，getRankOfNumber(x) 是查询从最小值到 x 的频次总和，正好对应树状数组的“单点更新 + 前缀和查询”。

c[i] 保存以 i 为右端点、长度为 lowbit(i) 的一段频次和。更新位置 i 时，通过 i += lowbit(i) 依次更新所有包含它的父区间；查询前缀时，通过 i -= lowbit(i) 把前缀拆成互不重叠的区间并累加。

不变量是：任何时刻，树状数组表示的底层频次数组都与已 track 的数据流完全一致。于是查询 x + 1 得到的就是原值区间 [0, x] 的总频次，天然包含所有等于 x 的重复项。

解题步骤

按最大值域创建容量足够的树状数组，下标 0 留空。

track(x) 调用 update(x + 1, 1)；重复 track 会在同一位置继续累加。

update 从当前下标向上跳父节点，把沿途区间和都加一。

getRankOfNumber(x) 调用 query(x + 1)，累加该下标及其所有前驱块。

依次 track(3)、track(1)、track(4)、track(4) 后，底层频次中 1 有一次、3 有一次、4 有两次。getRankOfNumber(2) 查询 [0,2] 得 1；getRankOfNumber(4) 查询 [0,4] 得 4，两个 4 都被计入。

代码实现

// 树状数组支持单点增加和频次前缀和查询。
class BinaryIndexedTree {
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void update(int x, int delta) {
        for (; x <= n; x += x & -x) {
            c[x] += delta;
        }
    }

    public int query(int x) {
        int s = 0;
        for (; x > 0; x -= x & -x) {
            s += c[x];
        }
        return s;
    }
}

class StreamRank {
    private BinaryIndexedTree tree = new BinaryIndexedTree(50010);

    public StreamRank() {
    }

    public void track(int x) {
        tree.update(x + 1, 1);
    }

    public int getRankOfNumber(int x) {
        return tree.query(x + 1);
    }
}

// 树状数组支持单点增加和频次前缀和查询。
type BinaryIndexedTree struct {
    n int
    c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
    return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}

func (bit *BinaryIndexedTree) update(x, delta int) {
    for ; x <= bit.n; x += x & -x {
        bit.c[x] += delta
    }
}

func (bit *BinaryIndexedTree) query(x int) int {
    s := 0
    for ; x > 0; x -= x & -x {
        s += bit.c[x]
    }
    return s
}

type StreamRank struct {
    tree *BinaryIndexedTree
}

func Constructor() StreamRank {
    return StreamRank{NewBinaryIndexedTree(50010)}
}

func (this *StreamRank) Track(x int) {
    this.tree.update(x+1, 1)
}

func (this *StreamRank) GetRankOfNumber(x int) int {
    return this.tree.query(x + 1)
}

复杂度分析

时间复杂度：设值域大小为 U，track 与 getRankOfNumber 都是 $O(\log U)$；本题 U 固定约 50001。

空间复杂度：$O(U)$，用于保存树状数组；与当前数据流长度无关。

关键点总结

“秩 = 小于等于某值的数量”就是频次数组的前缀和；动态单点插入 + 前缀查询优先考虑树状数组。

x + 1 不是随意偏移，而是把合法值 0 映射到树状数组的第一个有效下标，避免 lowbit(0) 死循环。

面试追问若值域未知，可用带子树大小的平衡搜索树，或离线收集操作后坐标压缩再建树状数组。

若把查询改成“严格小于 x”，只需查询映射后的 x，而不是 x + 1；等号直接体现在前缀右端点上。

易错点总结

直接用原值 0 作为树状数组下标：更新循环中 x += x & -x 永远加 0，程序死循环。

查询 x 而不是 x + 1：会变成统计严格小于 x，样例中等于 x 的元素全部漏掉。

把频次写成 1 而不是累加 1：重复 track(4) 被覆盖，查询 4 少计重复项。

树容量只开到 50001，却访问偏移后的最大值下标：原值 50000 映射到 50001，数组与内部 n 都必须覆盖该位置。

相似题目

题目	难度	考察点
307. 区域和检索 - 数组可修改	中等	树状数组的单点更新与区间查询
315. 计算右侧小于当前元素的个数	困难	离线倒序插入并查询前缀频次
1649. 通过指令创建有序数组	困难	动态统计两侧排名