尧图网站开发 
前两天一个学弟发来一道笔试题标题写着“实时排名”他说第一反应很简单——每次查询的时候把所有人按分数从高到低排个序然后输出排名不就行了结果一提交数据一大直接超时。我听完就笑了这题表面上叫“排名”实际考的根本不是排序而是“如何在频繁更新的数据流里快速知道某个人排第几”。这道题恰好是2026年携程暑期实习3月29日开发岗和算法岗的第二题题型非常典型适合所有正在准备大厂笔试的同学反复刷。这篇文章我会把题目还原清楚给出完整可跑的Java、C、Python解法再聊一聊这题背后真正想考察的数据结构思维。1. 题目还原实时排名本质上是一道数据结构题1.1 题目场景与输入输出约定原始题干的完整文本我没有拿到但根据标题、岗位方向和这类实时排名题的常见出题套路可以把题意还原得八九不离十。场景通常是某个比赛系统或者在线判题系统里有N个选手初始分数为0之后会进行M次操作每次操作要么是“给某个选手增加/减少一定分数”要么是“查询某个选手当前排名是多少”。输入格式基本可以约定为第一行两个整数 N 和 M代表选手人数和操作次数。 接下来 M 行每行格式如下 0 id x表示给编号为 id 的选手增加 x 分x 可以为负数 1 id表示查询编号为 id 的选手当前实时排名排名规则一般按分数从高到低排列分数相同则并列也就是说某人的排名 分数严格高于该选手的人数 1。输出每次查询操作的实时排名结果。这种问法在真实业务里特别常见游戏礼包排行榜、直播带货小时榜、赛事积分榜用户看到的名次都是“实时排名”背后不可能每次打开页面就把全量用户重新排一次序那样几千万用户早就把数据库打爆了。1.2 “实时排名”不是排序题而是统计题这是整道题最关键的认知转换。很多人第一反应是每次操作完了把所有人的分数排序然后遍历一遍找到目标选手的位置输出下标这个思路没错但从算法复杂度角度看完全是灾难。只要M次操作里有一半是查询每次都排一次序复杂度就是O(M * N log N)。当N和M都来到10^5量级5乘以10的10次方级别的计算量任何评测系统都不可能放你过去。需要换个角度看问题一个人排名第几名本质上是看“有多少人的分数比我高”。这不再是一个排序问题而是一个计数问题。只要我能快速地知道“分数大于某个值的人数”我就能立刻算出排名。于是问题转化为维护一个动态分数集合支持单点修改某人的分数变化并支持查询“分数严格大于v的人数”。这类问题正好落在树状数组、线段树这类前缀和统计型数据结构的射程范围内。所以这道题虽然名字叫“排名”考的是数据结构基础知识动态维护频率分布。1.3 数据范围决定算法选择做题第一步永远是估算数据范围而不是急着写代码。我把常见的几种数据范围和解法做了一张对照表笔试时可以直接对号入座数据范围可行方案复杂度N, M ≤ 100每次查询直接扫描并统计O(M*N)N, M ≤ 5000每次操作后暴力排序O(M*N log N)N, M ≤ 10^5 且分数只增不减树状数组/线段树 离散化O((NM) log (NM))N, M ≤ 10^5 且分数可加可减树状数组/线段树 离散化O((NM) log (NM))框架笔试的数据量一般都在10^5级别所以下面所有讲解和代码都围绕“离散化 树状数组”这个正解来展开。2. 两种常见错误解法先帮你排排雷2.1 错误一每次查询都重新排序这是大部分人的第一直觉也是最容易超时的写法。写起来很舒服三五行就搞定# 伪代码复杂度爆炸 for op in operations: if op 查询: sorted_scores sorted(scores, reverseTrue) print(sorted_scores.index(scores[id]) 1)问题不在于逻辑错而在于完全没有考虑代价。每次排序都是O(N log N)如果M是10^5N也是10^5即使一半操作是查询也会有5万次全量排序。5万乘以10万乘以17这个计算量已经远远超出了单机几秒能完成的范畴。我在帮学弟review代码的时候发现他其实也知道该优化但总抱着“评测数据可能比较小”的侥幸心理。笔试题的评测数据从来不会让暴力解法轻易过关否则就失去了考察的意义。这道题想筛选的是你能不能在压力下从“能跑”走向“能扛住大流量”。2.2 错误二维护一个堆或有序列表还有一部分选手想到用堆来维护TopK或者用Python的SortedList/Java的TreeMap。堆只能保证拿到当前分数最高的前K个人但题目要求的是“任意指定选手的实时排名”堆结构并不支持快速查询“某人排第几”。比如有10万个选手我只想查编号为12345的选手现在排第几堆能告诉我的只有堆顶是谁或者前K个是谁。如果KN, 那本质上又退化成了全量排序的变体。还有一个隐蔽的问题分数发生更新时堆的任意删除和更新实现非常容易写错笔试现场调试起来极其痛苦。SortedList这种有序列表的插入删除虽然是O(log N)级别的查找但是底层向量的插入删除需要移动元素最坏可以达到O(N)数据量一大照样吃不住。TreeMap只能根据key找到某个分数的位置但没法高效汇总“大于某个分数的总数”——除非你额外维护子树节点数量这其实就是自己手搓平衡树的活了。2.3 复杂度账本要算明白三种方案大家心里有数之后我把复杂度列成一张表笔试前扫一眼能帮助形成条件反射方案单次更新单次查询适合数据量全量排序O(1)O(N log N)N ≤ 5000有序列表O(N)O(log N)N ≤ 10000平衡树O(log N)O(log N)N ≤ 10^5树状数组 离散化O(log N)O(log N)N ≤ 10^5 甚至更大树状数组的优势在于代码量远小于平衡树逻辑也更不容易出错是笔试现场性价比最高的做法。3. 正解核心离散化 树状数组怎么组合3.1 把排名计算改写成前缀和问题假设我把每个人的分数放进一个桶数组cnt中cnt[i]表示“分数为i的人数”。那么“分数大于v的人数”就是cnt[v1] cnt[v2] ... cnt[maxScore]。实时排名就是rank 严格大于当前分数的总人数 1 (总人数 - 小于等于当前分数的人数) 1如果能够快速求出“小于等于某个分数的人数”这个排名就出来了。而这个“小于等于”的累计效果恰好是前缀和的经典场景。问题是分数的取值范围可能非常大比如10^9直接开数组开不下。离散化就是用来压缩值域的。所有可能出现的分数点只有初始的0和每次更新后产生的新分数总数不超过M1个。把这最多M1个分数点排序去重映射到1..K的紧凑下标上数组大小瞬间从10^9压缩到10^5级别。每个选手的分数无论怎么变都能在这个紧凑的坐标体系里找到一个确定的位置。3.2 树状数组如何支持“单点修改 前缀求和”树状数组是一个非常适合这种场景的数据结构它比线段树写起来短得多常数也小。它的核心思想是每个下标i存储的不是单纯的a[i]而是从某个位置到i的一段区间和这个区间长度就是lowbit(i) i (-i)。更新操作很直接当某个分数点的人数变化时从这个下标开始不断向上跳跃把所有覆盖该位置的区间节点一起更新跳跃步长就是lowbit。查询前缀和则反过来从当前下标开始不断向下剥离lowbit区间把沿途的区间和累加起来。两个操作都是O(log K)的复杂度K是离散化后的分数种类数最多M1。打个比方树状数组的更新就像往一个流水线上逐个闸口补货每个闸口只管一段区间的存量查询的时候顺着闸口一路向下收集区间的累计数不需要关心每个人的具体位置只需要知道每个分数段的人数汇总。3.3 离散化的具体操作步骤离散化需要两步第一预先模拟一遍所有“增加分数”的操作把每次操作之后的累计分数加入候选列表第二对候选列表排序去重获得每个分数点的唯一下标。为什么必须预先把所有分数收集起来因为后续查询和更新的过程中某个分数可能还没有出现但之后某次操作会让某个选手到达这个分数。树状数组的大小在开始时必须固定中途动态扩容会导致下标失效非常麻烦。先离线收集、再统一编号是这类题的标准套路。具体到代码里就是开一个vector或者List先塞入初始分数0然后遍历所有操作是加分操作就把累加后的分数push进去。全部处理完后排序去重并用二分查找把每个真实分数映射为数组下标。竞赛里通常用lower_bound或者Collections.binarySearch来完成映射。4. Java / C / Python 三版完整代码4.1 Java版本import java.util.*; public class Main { static class BIT { int n; int[] c; BIT(int n) { this.n n; c new int[n 1]; } void add(int i, int v) { while (i n) { c[i] v; i i -i; } } int sum(int i) { int s 0; while (i 0) { s c[i]; i - i -i; } return s; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); long[] score new long[n 1]; int[] op new int[m]; int[] pid new int[m]; long[] val new long[m]; ListLong all new ArrayList(); all.add(0L); for (int i 0; i m; i) { op[i] sc.nextInt(); pid[i] sc.nextInt(); if (op[i] 0) { val[i] sc.nextLong(); score[pid[i]] val[i]; all.add(score[pid[i]]); } } Collections.sort(all); ListLong coords new ArrayList(); for (int i 0; i all.size(); i) { if (i 0 || !all.get(i).equals(all.get(i - 1))) { coords.add(all.get(i)); } } int size coords.size(); BIT bit new BIT(size); Arrays.fill(score, 0); int zeroIdx Collections.binarySearch(coords, 0L) 1; for (int i 1; i n; i) { bit.add(zeroIdx, 1); } for (int i 0; i m; i) { int p pid[i]; if (op[i] 0) { int oldIdx Collections.binarySearch(coords, score[p]) 1; bit.add(oldIdx, -1); score[p] val[i]; int newIdx Collections.binarySearch(coords, score[p]) 1; bit.add(newIdx, 1); } else { int idx Collections.binarySearch(coords, score[p]) 1; int rank n - bit.sum(idx) 1; System.out.println(rank); } } } }这份代码有几个地方需要解释。第一分数用long存而不是int因为加分操作可能多次累加int会溢出。第二所有分数点收集完毕后排序去重后续通过Collections.binarySearch做映射返回下标要加1因为树状数组的下标从1开始。第三初始分数0对应的下标一次性把N个人全部插入BIT中。4.2 C版本#include bits/stdc.h using namespace std; using ll long long; struct BIT { int n; vectorint c; BIT(int n) : n(n), c(n 1, 0) {} void add(int i, int v) { while (i n) { c[i] v; i i -i; } } int sum(int i) { int res 0; while (i 0) { res c[i]; i - i -i; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorll score(n 1, 0); vectorint op(m), id(m); vectorll x(m); vectorll all; all.push_back(0); for (int i 0; i m; i) { cin op[i] id[i]; if (op[i] 0) { cin x[i]; score[id[i]] x[i]; all.push_back(score[id[i]]); } } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int size (int)all.size(); BIT bit(size); fill(score.begin(), score.end(), 0); auto getIdx [](ll v) { return int(lower_bound(all.begin(), all.end(), v) - all.begin()) 1; }; int zeroIdx getIdx(0); for (int i 1; i n; i) { bit.add(zeroIdx, 1); } for (int i 0; i m; i) { int p id[i]; if (op[i] 0) { int oldIdx getIdx(score[p]); bit.add(oldIdx, -1); score[p] x[i]; int newIdx getIdx(score[p]); bit.add(newIdx, 1); } else { int idx getIdx(score[p]); int rank n - bit.sum(idx) 1; cout rank \n; } } return 0; }C版本和Java版本思路完全一致。需要注意这里用了lambda表达式getIdx来统一完成分数到下标的映射避免了重复写lower_bound的麻烦。输入输出我关掉了同步并且用\n输出这是C刷题的基本习惯。4.3 Python版本标准BIT解法import sys from bisect import bisect_left def main(): input sys.stdin.readline n, m map(int, input().split()) score [0] * (n 1) ops [] all_values [0] for _ in range(m): parts list(map(int, input().split())) op, p parts[0], parts[1] if op 0: x parts[2] score[p] x all_values.append(score[p]) ops.append((op, p, x)) else: ops.append((op, p, 0)) coords sorted(set(all_values)) size len(coords) bit [0] * (size 1) def add(i, v): while i size: bit[i] v i i -i def query(i): s 0 while i 0: s bit[i] i - i -i return s score [0] * (n 1) zero_idx bisect_left(coords, 0) 1 for i in range(1, n 1): add(zero_idx, 1) for op, p, x in ops: if op 0: old_idx bisect_left(coords, score[p]) 1 add(old_idx, -1) score[p] x new_idx bisect_left(coords, score[p]) 1 add(new_idx, 1) else: idx bisect_left(coords, score[p]) 1 rank n - query(idx) 1 print(rank) if __name__ __main__: main()Python代码的核心逻辑和前两个版本对齐使用bisect_left做分数到下标映射。需要注意Python在大数据量下的常数较大如果评测数据特别大建议用PyPy提交。4.4 Python偷懒版bisect有序列表数据量小时可用from bisect import bisect_right, insort n, m map(int, input().split()) scores [0] * (n 1) sorted_scores [0] * n for _ in range(m): parts list(map(int, input().split())) op, p parts[0], parts[1] if op 0: x parts[2] old scores[p] sorted_scores.remove(old) scores[p] x insort(sorted_scores, scores[p]) else: rank n - bisect_right(sorted_scores, scores[p]) 1 print(rank)这个版本代码量小很多思路是始终维护一个升序列表更新时删掉旧分数插入新分数。查询时用bisect_right得到“小于等于自己分数的人数”再用总人数减去。但它隐藏着一个O(N)级别的remove操作数据量到10^5后会非常吃力。笔试时间紧来不及写BIT的时候可以拿来保底但正式解法一定推荐标准BIT版本。4.5 自测样例我准备了一份小样例可以快速验证代码是否正确输入 5 6 0 1 10 0 2 15 0 3 5 1 1 1 2 0 1 -5 1 1手动模拟三个加分操作后选手1、2、3的分数分别为10、15、5查询选手1严格大于10的只有选手2排名2查询选手2没人高于15排名1选手1减5分后分数为5此时分数高于5的有选手215选手1与选手3并列第二查询结果应为2预期输出2 1 25. 笔试现场最容易踩的四个边界坑5.1 并列分数时排名怎么算这是增长率码面试的经典问题了。题目里如果没说特殊规则默认就是“分数相同排名相同”比如两个人都是第二那下一个就是第四而不是第三。用代码表达就是严格大于自己分数的人数加一。但是如果题目改成“同分时按编号小优先”或者“同分时按达到该分数的时间早优先”那数据结构就不能只统计分数人数了得在分数后面再叠加一个次要键比如把分数编码成“分数 * 时间戳 编号”再离散化。押题时可以把这个变体想明白实际做题时以题面为准。5.2 先更新还是先查询时序不能乱模拟操作时要非常小心。对于更新操作必须先找到选手当前分数对应的下标在BIT中减1然后再累加新分数找到新下标加1。如果先把score[p]改了再拿着新分数去定位旧下标二分定位就会出错导致BIT里的人数分布和真实情况不一致。有些同学喜欢写成先加分再统一更新这种写法在这个场景下行不通。更新操作和查询操作的时序就是“保持每个时刻BIT中的数据都是当前最新状态”每一步都不能马虎。5.3 分数累计溢出问题笔试给的分数增量可能是正数也可能是负数而且会多次累加。int在Java和C里都是32位上限约21亿几次大增量累加就可能爆掉。保险起见分数用long long或者Java的long来存。离散化的坐标数组也要用64位类型否则二分查找的时候会因为溢出而找不到正确下标。5.4 树状数组下标从1开始树状数组的实现依赖“下标0不能参与更新”的性质如果二分查找映射出来是0再传入updatewhile循环会死循环。所以在所有getIdx操作返回时都要加1。Java里Collections.binarySearch的返回值可能是负的但因为我们收集的所有分数点都来自真实操作一定存在于坐标数组中所以返回结果一定是非负索引加1之后必然落在1..K的合法区间内。5.5 用对拍测试验证正确性光靠样例自测不保险笔试前最好养成写对拍脚本的习惯写一个暴力算法再写一个优化算法然后随机生成很多组小数据比较两者输出是否完全一致。我这里给一个Python对拍的思路import random def brute(n, ops): score [0] * n out [] for op in ops: if op[0] 0: score[op[1]] op[2] else: out.append(sum(1 for v in score if v score[op[1]]) 1) return out # 随机生成操作 与 fast 版本的输出逐一比对对拍的价值在于它能用大量随机数据自动找出你处理边界条件时的笔误。平时练习多写对拍笔试现场会稳定很多。6. 如果题目再进阶一点怎么应对6.1 同时要求输出TopK榜单有些实时排名系统不只查某个人的名次还要求把实时前K名展示出来。树状数组做前缀和很快但要从全局中找到第K大、第K小还需要在BIT上做二分查找从最高位开始尝试跳跃累加区间的计数直到找到某个下标刚好让前缀总数覆盖目标名次。这是在线段树/树状数组上进行“二分计数”的经典扩展代码量会再上一个台阶但思想还是前缀和统计。6.2 如果选手可以中途加入题目如果设定为“新选手可以随时注册”那离散化坐标时就必须把所有可能新增的选手初始分数0预先塞进坐标列表。只要坐标集合一开始覆盖住所有将来可能出现的分数点中途新增选手就只是在BIT对应位置加1并不影响已经算好的离散化结构。6.3 工程里的实时排名为什么不这么写真实业务系统做实时榜单一般不会自研BIT直接用Redis的有序集合ZSET更常见底层是跳表支持按分数排序和快速查询某个成员的排名复杂度同样是O(log N)。笔试考BIT不是为了让你工作中手写这玩意儿而是考察你能不能把一个业务问题抽象成数据结构的经典模型。能抽象出来选BIT还是ZSET只是战场不同而已。最后再分享一点个人体会这道题我后来自己完整写了一遍发现最有价值的不是背模板而是养成“先算数据范围再动手”的习惯。很多人做笔试丢分不是因为不会算法而是被“实时排名”四个字带偏了方向一头扎进排序里出不来。把“排名”翻译成“计数”把“排序”翻译成“前缀和”这类题就稳了。 
前两天一个学弟发来一道笔试题标题写着“实时排名”他说第一反应很简单——每次查询的时候把所有人按分数从高到低排个序然后输出排名不就行了结果一提交数据一大直接超时。我听完就笑了这题表面上叫“排名”实际考的根本不是排序而是“如何在频繁更新的数据流里快速知道某个人排第几”。这道题恰好是2026年携程暑期实习3月29日开发岗和算法岗的第二题题型非常典型适合所有正在准备大厂笔试的同学反复刷。这篇文章我会把题目还原清楚给出完整可跑的Java、C、Python解法再聊一聊这题背后真正想考察的数据结构思维。1. 题目还原实时排名本质上是一道数据结构题1.1 题目场景与输入输出约定原始题干的完整文本我没有拿到但根据标题、岗位方向和这类实时排名题的常见出题套路可以把题意还原得八九不离十。场景通常是某个比赛系统或者在线判题系统里有N个选手初始分数为0之后会进行M次操作每次操作要么是“给某个选手增加/减少一定分数”要么是“查询某个选手当前排名是多少”。输入格式基本可以约定为第一行两个整数 N 和 M代表选手人数和操作次数。 接下来 M 行每行格式如下 0 id x表示给编号为 id 的选手增加 x 分x 可以为负数 1 id表示查询编号为 id 的选手当前实时排名排名规则一般按分数从高到低排列分数相同则并列也就是说某人的排名 分数严格高于该选手的人数 1。输出每次查询操作的实时排名结果。这种问法在真实业务里特别常见游戏礼包排行榜、直播带货小时榜、赛事积分榜用户看到的名次都是“实时排名”背后不可能每次打开页面就把全量用户重新排一次序那样几千万用户早就把数据库打爆了。1.2 “实时排名”不是排序题而是统计题这是整道题最关键的认知转换。很多人第一反应是每次操作完了把所有人的分数排序然后遍历一遍找到目标选手的位置输出下标这个思路没错但从算法复杂度角度看完全是灾难。只要M次操作里有一半是查询每次都排一次序复杂度就是O(M * N log N)。当N和M都来到10^5量级5乘以10的10次方级别的计算量任何评测系统都不可能放你过去。需要换个角度看问题一个人排名第几名本质上是看“有多少人的分数比我高”。这不再是一个排序问题而是一个计数问题。只要我能快速地知道“分数大于某个值的人数”我就能立刻算出排名。于是问题转化为维护一个动态分数集合支持单点修改某人的分数变化并支持查询“分数严格大于v的人数”。这类问题正好落在树状数组、线段树这类前缀和统计型数据结构的射程范围内。所以这道题虽然名字叫“排名”考的是数据结构基础知识动态维护频率分布。1.3 数据范围决定算法选择做题第一步永远是估算数据范围而不是急着写代码。我把常见的几种数据范围和解法做了一张对照表笔试时可以直接对号入座数据范围可行方案复杂度N, M ≤ 100每次查询直接扫描并统计O(M*N)N, M ≤ 5000每次操作后暴力排序O(M*N log N)N, M ≤ 10^5 且分数只增不减树状数组/线段树 离散化O((NM) log (NM))N, M ≤ 10^5 且分数可加可减树状数组/线段树 离散化O((NM) log (NM))框架笔试的数据量一般都在10^5级别所以下面所有讲解和代码都围绕“离散化 树状数组”这个正解来展开。2. 两种常见错误解法先帮你排排雷2.1 错误一每次查询都重新排序这是大部分人的第一直觉也是最容易超时的写法。写起来很舒服三五行就搞定# 伪代码复杂度爆炸 for op in operations: if op 查询: sorted_scores sorted(scores, reverseTrue) print(sorted_scores.index(scores[id]) 1)问题不在于逻辑错而在于完全没有考虑代价。每次排序都是O(N log N)如果M是10^5N也是10^5即使一半操作是查询也会有5万次全量排序。5万乘以10万乘以17这个计算量已经远远超出了单机几秒能完成的范畴。我在帮学弟review代码的时候发现他其实也知道该优化但总抱着“评测数据可能比较小”的侥幸心理。笔试题的评测数据从来不会让暴力解法轻易过关否则就失去了考察的意义。这道题想筛选的是你能不能在压力下从“能跑”走向“能扛住大流量”。2.2 错误二维护一个堆或有序列表还有一部分选手想到用堆来维护TopK或者用Python的SortedList/Java的TreeMap。堆只能保证拿到当前分数最高的前K个人但题目要求的是“任意指定选手的实时排名”堆结构并不支持快速查询“某人排第几”。比如有10万个选手我只想查编号为12345的选手现在排第几堆能告诉我的只有堆顶是谁或者前K个是谁。如果KN, 那本质上又退化成了全量排序的变体。还有一个隐蔽的问题分数发生更新时堆的任意删除和更新实现非常容易写错笔试现场调试起来极其痛苦。SortedList这种有序列表的插入删除虽然是O(log N)级别的查找但是底层向量的插入删除需要移动元素最坏可以达到O(N)数据量一大照样吃不住。TreeMap只能根据key找到某个分数的位置但没法高效汇总“大于某个分数的总数”——除非你额外维护子树节点数量这其实就是自己手搓平衡树的活了。2.3 复杂度账本要算明白三种方案大家心里有数之后我把复杂度列成一张表笔试前扫一眼能帮助形成条件反射方案单次更新单次查询适合数据量全量排序O(1)O(N log N)N ≤ 5000有序列表O(N)O(log N)N ≤ 10000平衡树O(log N)O(log N)N ≤ 10^5树状数组 离散化O(log N)O(log N)N ≤ 10^5 甚至更大树状数组的优势在于代码量远小于平衡树逻辑也更不容易出错是笔试现场性价比最高的做法。3. 正解核心离散化 树状数组怎么组合3.1 把排名计算改写成前缀和问题假设我把每个人的分数放进一个桶数组cnt中cnt[i]表示“分数为i的人数”。那么“分数大于v的人数”就是cnt[v1] cnt[v2] ... cnt[maxScore]。实时排名就是rank 严格大于当前分数的总人数 1 (总人数 - 小于等于当前分数的人数) 1如果能够快速求出“小于等于某个分数的人数”这个排名就出来了。而这个“小于等于”的累计效果恰好是前缀和的经典场景。问题是分数的取值范围可能非常大比如10^9直接开数组开不下。离散化就是用来压缩值域的。所有可能出现的分数点只有初始的0和每次更新后产生的新分数总数不超过M1个。把这最多M1个分数点排序去重映射到1..K的紧凑下标上数组大小瞬间从10^9压缩到10^5级别。每个选手的分数无论怎么变都能在这个紧凑的坐标体系里找到一个确定的位置。3.2 树状数组如何支持“单点修改 前缀求和”树状数组是一个非常适合这种场景的数据结构它比线段树写起来短得多常数也小。它的核心思想是每个下标i存储的不是单纯的a[i]而是从某个位置到i的一段区间和这个区间长度就是lowbit(i) i (-i)。更新操作很直接当某个分数点的人数变化时从这个下标开始不断向上跳跃把所有覆盖该位置的区间节点一起更新跳跃步长就是lowbit。查询前缀和则反过来从当前下标开始不断向下剥离lowbit区间把沿途的区间和累加起来。两个操作都是O(log K)的复杂度K是离散化后的分数种类数最多M1。打个比方树状数组的更新就像往一个流水线上逐个闸口补货每个闸口只管一段区间的存量查询的时候顺着闸口一路向下收集区间的累计数不需要关心每个人的具体位置只需要知道每个分数段的人数汇总。3.3 离散化的具体操作步骤离散化需要两步第一预先模拟一遍所有“增加分数”的操作把每次操作之后的累计分数加入候选列表第二对候选列表排序去重获得每个分数点的唯一下标。为什么必须预先把所有分数收集起来因为后续查询和更新的过程中某个分数可能还没有出现但之后某次操作会让某个选手到达这个分数。树状数组的大小在开始时必须固定中途动态扩容会导致下标失效非常麻烦。先离线收集、再统一编号是这类题的标准套路。具体到代码里就是开一个vector或者List先塞入初始分数0然后遍历所有操作是加分操作就把累加后的分数push进去。全部处理完后排序去重并用二分查找把每个真实分数映射为数组下标。竞赛里通常用lower_bound或者Collections.binarySearch来完成映射。4. Java / C / Python 三版完整代码4.1 Java版本import java.util.*; public class Main { static class BIT { int n; int[] c; BIT(int n) { this.n n; c new int[n 1]; } void add(int i, int v) { while (i n) { c[i] v; i i -i; } } int sum(int i) { int s 0; while (i 0) { s c[i]; i - i -i; } return s; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); long[] score new long[n 1]; int[] op new int[m]; int[] pid new int[m]; long[] val new long[m]; ListLong all new ArrayList(); all.add(0L); for (int i 0; i m; i) { op[i] sc.nextInt(); pid[i] sc.nextInt(); if (op[i] 0) { val[i] sc.nextLong(); score[pid[i]] val[i]; all.add(score[pid[i]]); } } Collections.sort(all); ListLong coords new ArrayList(); for (int i 0; i all.size(); i) { if (i 0 || !all.get(i).equals(all.get(i - 1))) { coords.add(all.get(i)); } } int size coords.size(); BIT bit new BIT(size); Arrays.fill(score, 0); int zeroIdx Collections.binarySearch(coords, 0L) 1; for (int i 1; i n; i) { bit.add(zeroIdx, 1); } for (int i 0; i m; i) { int p pid[i]; if (op[i] 0) { int oldIdx Collections.binarySearch(coords, score[p]) 1; bit.add(oldIdx, -1); score[p] val[i]; int newIdx Collections.binarySearch(coords, score[p]) 1; bit.add(newIdx, 1); } else { int idx Collections.binarySearch(coords, score[p]) 1; int rank n - bit.sum(idx) 1; System.out.println(rank); } } } }这份代码有几个地方需要解释。第一分数用long存而不是int因为加分操作可能多次累加int会溢出。第二所有分数点收集完毕后排序去重后续通过Collections.binarySearch做映射返回下标要加1因为树状数组的下标从1开始。第三初始分数0对应的下标一次性把N个人全部插入BIT中。4.2 C版本#include bits/stdc.h using namespace std; using ll long long; struct BIT { int n; vectorint c; BIT(int n) : n(n), c(n 1, 0) {} void add(int i, int v) { while (i n) { c[i] v; i i -i; } } int sum(int i) { int res 0; while (i 0) { res c[i]; i - i -i; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorll score(n 1, 0); vectorint op(m), id(m); vectorll x(m); vectorll all; all.push_back(0); for (int i 0; i m; i) { cin op[i] id[i]; if (op[i] 0) { cin x[i]; score[id[i]] x[i]; all.push_back(score[id[i]]); } } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int size (int)all.size(); BIT bit(size); fill(score.begin(), score.end(), 0); auto getIdx [](ll v) { return int(lower_bound(all.begin(), all.end(), v) - all.begin()) 1; }; int zeroIdx getIdx(0); for (int i 1; i n; i) { bit.add(zeroIdx, 1); } for (int i 0; i m; i) { int p id[i]; if (op[i] 0) { int oldIdx getIdx(score[p]); bit.add(oldIdx, -1); score[p] x[i]; int newIdx getIdx(score[p]); bit.add(newIdx, 1); } else { int idx getIdx(score[p]); int rank n - bit.sum(idx) 1; cout rank \n; } } return 0; }C版本和Java版本思路完全一致。需要注意这里用了lambda表达式getIdx来统一完成分数到下标的映射避免了重复写lower_bound的麻烦。输入输出我关掉了同步并且用\n输出这是C刷题的基本习惯。4.3 Python版本标准BIT解法import sys from bisect import bisect_left def main(): input sys.stdin.readline n, m map(int, input().split()) score [0] * (n 1) ops [] all_values [0] for _ in range(m): parts list(map(int, input().split())) op, p parts[0], parts[1] if op 0: x parts[2] score[p] x all_values.append(score[p]) ops.append((op, p, x)) else: ops.append((op, p, 0)) coords sorted(set(all_values)) size len(coords) bit [0] * (size 1) def add(i, v): while i size: bit[i] v i i -i def query(i): s 0 while i 0: s bit[i] i - i -i return s score [0] * (n 1) zero_idx bisect_left(coords, 0) 1 for i in range(1, n 1): add(zero_idx, 1) for op, p, x in ops: if op 0: old_idx bisect_left(coords, score[p]) 1 add(old_idx, -1) score[p] x new_idx bisect_left(coords, score[p]) 1 add(new_idx, 1) else: idx bisect_left(coords, score[p]) 1 rank n - query(idx) 1 print(rank) if __name__ __main__: main()Python代码的核心逻辑和前两个版本对齐使用bisect_left做分数到下标映射。需要注意Python在大数据量下的常数较大如果评测数据特别大建议用PyPy提交。4.4 Python偷懒版bisect有序列表数据量小时可用from bisect import bisect_right, insort n, m map(int, input().split()) scores [0] * (n 1) sorted_scores [0] * n for _ in range(m): parts list(map(int, input().split())) op, p parts[0], parts[1] if op 0: x parts[2] old scores[p] sorted_scores.remove(old) scores[p] x insort(sorted_scores, scores[p]) else: rank n - bisect_right(sorted_scores, scores[p]) 1 print(rank)这个版本代码量小很多思路是始终维护一个升序列表更新时删掉旧分数插入新分数。查询时用bisect_right得到“小于等于自己分数的人数”再用总人数减去。但它隐藏着一个O(N)级别的remove操作数据量到10^5后会非常吃力。笔试时间紧来不及写BIT的时候可以拿来保底但正式解法一定推荐标准BIT版本。4.5 自测样例我准备了一份小样例可以快速验证代码是否正确输入 5 6 0 1 10 0 2 15 0 3 5 1 1 1 2 0 1 -5 1 1手动模拟三个加分操作后选手1、2、3的分数分别为10、15、5查询选手1严格大于10的只有选手2排名2查询选手2没人高于15排名1选手1减5分后分数为5此时分数高于5的有选手215选手1与选手3并列第二查询结果应为2预期输出2 1 25. 笔试现场最容易踩的四个边界坑5.1 并列分数时排名怎么算这是增长率码面试的经典问题了。题目里如果没说特殊规则默认就是“分数相同排名相同”比如两个人都是第二那下一个就是第四而不是第三。用代码表达就是严格大于自己分数的人数加一。但是如果题目改成“同分时按编号小优先”或者“同分时按达到该分数的时间早优先”那数据结构就不能只统计分数人数了得在分数后面再叠加一个次要键比如把分数编码成“分数 * 时间戳 编号”再离散化。押题时可以把这个变体想明白实际做题时以题面为准。5.2 先更新还是先查询时序不能乱模拟操作时要非常小心。对于更新操作必须先找到选手当前分数对应的下标在BIT中减1然后再累加新分数找到新下标加1。如果先把score[p]改了再拿着新分数去定位旧下标二分定位就会出错导致BIT里的人数分布和真实情况不一致。有些同学喜欢写成先加分再统一更新这种写法在这个场景下行不通。更新操作和查询操作的时序就是“保持每个时刻BIT中的数据都是当前最新状态”每一步都不能马虎。5.3 分数累计溢出问题笔试给的分数增量可能是正数也可能是负数而且会多次累加。int在Java和C里都是32位上限约21亿几次大增量累加就可能爆掉。保险起见分数用long long或者Java的long来存。离散化的坐标数组也要用64位类型否则二分查找的时候会因为溢出而找不到正确下标。5.4 树状数组下标从1开始树状数组的实现依赖“下标0不能参与更新”的性质如果二分查找映射出来是0再传入updatewhile循环会死循环。所以在所有getIdx操作返回时都要加1。Java里Collections.binarySearch的返回值可能是负的但因为我们收集的所有分数点都来自真实操作一定存在于坐标数组中所以返回结果一定是非负索引加1之后必然落在1..K的合法区间内。5.5 用对拍测试验证正确性光靠样例自测不保险笔试前最好养成写对拍脚本的习惯写一个暴力算法再写一个优化算法然后随机生成很多组小数据比较两者输出是否完全一致。我这里给一个Python对拍的思路import random def brute(n, ops): score [0] * n out [] for op in ops: if op[0] 0: score[op[1]] op[2] else: out.append(sum(1 for v in score if v score[op[1]]) 1) return out # 随机生成操作 与 fast 版本的输出逐一比对对拍的价值在于它能用大量随机数据自动找出你处理边界条件时的笔误。平时练习多写对拍笔试现场会稳定很多。6. 如果题目再进阶一点怎么应对6.1 同时要求输出TopK榜单有些实时排名系统不只查某个人的名次还要求把实时前K名展示出来。树状数组做前缀和很快但要从全局中找到第K大、第K小还需要在BIT上做二分查找从最高位开始尝试跳跃累加区间的计数直到找到某个下标刚好让前缀总数覆盖目标名次。这是在线段树/树状数组上进行“二分计数”的经典扩展代码量会再上一个台阶但思想还是前缀和统计。6.2 如果选手可以中途加入题目如果设定为“新选手可以随时注册”那离散化坐标时就必须把所有可能新增的选手初始分数0预先塞进坐标列表。只要坐标集合一开始覆盖住所有将来可能出现的分数点中途新增选手就只是在BIT对应位置加1并不影响已经算好的离散化结构。6.3 工程里的实时排名为什么不这么写真实业务系统做实时榜单一般不会自研BIT直接用Redis的有序集合ZSET更常见底层是跳表支持按分数排序和快速查询某个成员的排名复杂度同样是O(log N)。笔试考BIT不是为了让你工作中手写这玩意儿而是考察你能不能把一个业务问题抽象成数据结构的经典模型。能抽象出来选BIT还是ZSET只是战场不同而已。最后再分享一点个人体会这道题我后来自己完整写了一遍发现最有价值的不是背模板而是养成“先算数据范围再动手”的习惯。很多人做笔试丢分不是因为不会算法而是被“实时排名”四个字带偏了方向一头扎进排序里出不来。把“排名”翻译成“计数”把“排序”翻译成“前缀和”这类题就稳了。