applications · 真实应用

应用实例：这些结构究竟用在何处

前几页讲的是原理。这一页把它们放进两个可动手体验的真实场景：用树状数组做实时排行榜, 用二维前缀和做图像/热力图的矩形求和（积分图）。每个 demo 都将「换成朴素做法需多少代价」并列对照。

1 · 实时排行榜：查询名次（树状数组）

游戏 / 竞价排名 / 考试系统都要回答「分数 s 排第几名」。名次 = 比我分高的人数 + 1。朴素做法即便只做有序插入也要 $O(n)$ 次移动，查名次再扫一遍 $O(n)$ 。用树状数组（按分数桶计数）：加入是一次 update、查名次是一次前缀和，都只要 $O(\log C)$ （ $C$ 为分数上限）。本页分数取 1 到 16，查询至多 4 步、加入至多 5 个节点，榜单再大也不重排。

图 1-1 · 权值树状数组维护的实时排行榜。可加入分数并查询名次，右侧对照朴素做法的代价。

注 · 名次公式是 $\mathrm{rank}(s) = N - \mathrm{prefix}(s) + 1$ ，其中 $N$ 是总人数、 $\mathrm{prefix}(s)$ 是分数不超过 $s$ 的人数（BIT 前缀和）， $N - \mathrm{prefix}(s)$ 就是分数比 $s$ 高的人数。整张榜一个都不用重排。

2 · 积分图：任意矩形区域和 O(1)（二维前缀和）

一张热力图 / 灰度图，反复问「这个矩形框里的总和是多少」（图像模糊的滑窗、人脸检测的 Haar 特征）。朴素法把框里每个格子加一遍，框越大越慢。二维前缀和（积分图 / summed-area table） 预处理后，任意矩形和只需查 4 个角、两加两减，与框大小无关——这正是 OpenCV cv::integral() 所做的事。

图 2-1 · 积分图上任意矩形和的四角容斥。可拖动 4 个坐标框选矩形，读数给出

O(1)

公式的结果与朴素逐格相加的次数对照。

注 · 容斥公式是 $sum = P[r_2+1][c_2+1] - P[r_1][c_2+1] - P[r_2+1][c_1] + P[r_1][c_1]$ ：大矩形减去上、左两条，再把多减的左上角加回来。无论框是 2×2 还是 2000×2000，永远 4 次查表。

3 · 同一思路的其他落点

「预处理出区间聚合 → 把区间问题转化为端点之差 / 树上对数次访问」这一思路，在工程中反复出现：

逆序对计数：衡量序列错乱度 →

从右往左把元素插进权值树状数组，每插一个就 query 比它小的已出现个数——累加就是逆序对数。推荐系统用它衡量「推荐序 vs 实际点击序」错乱度， $O(n \log n)$ 取代 $O(n^2)$ 暴力。

扫描线：矩形面积并 / 重叠

一条竖线从左扫到右，用线段树 + lazy 维护「当前被覆盖的纵向长度」。EDA 芯片版图 DRC、GIS 地图图层叠加、网页元素碰撞检测都借助它把「众多矩形覆盖了多大面积」计算到 $O(n \log n)$ 。

批量调价 / 区间生效 →

「把这段时间所有商品涨 10%」「给某区段用户都 +100 积分」——区间整体修改 + 区间查询正是 lazy propagation 的典型用武之地：标记挂在高处，真正读到时才下推，修改一整段也只需 $O(\log n)$ 。

报表 / 监控的时间区间统计

「过去 7 天 GMV」「某时间窗错误率峰值」：静态历史用前缀和 $O(1)$ 取区间；边写边查则采用树状数组 / 线段树，把「实时扫描一段」降为对数级。

注 · 以上每个场景拆解开来，都是树状数组与线段树两页讲过的 update 与 query。