applications · 真实应用

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

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

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

游戏 / 竞价排名 / 考试系统都要回答「分数 s 排第几名」。名次 = 比我分高的人数 + 1。朴素做法：每加一个分数就把整张榜重排一遍 $O(n \log n)$ ；查名次再扫一遍 $O(n)$ 。用树状数组（按分数桶计数）：加入是一次 update、查名次是一次前缀和，都只要 $O(\log 上限)$ ——这里分数 1..16,每次恒定 4 步，榜单再大也不重排。

名次公式： $rank(s) = 总人数 - prefix(s) + 1$ ，其中 prefix(s) = 分数 ≤ s 的人数（BIT 前缀和）。 $总人数 - prefix(s)$ 就是分数比 s 高的人数。整张榜一个都不用重排，这正是树状数组在排行榜里的价值。

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

一张热力图 / 灰度图，反复问「这个矩形框里的总和是多少」（图像模糊的滑窗、人脸检测的 Haar 特征）。朴素法把框里每个格子加一遍，框越大越慢。二维前缀和（积分图 / summed-area table） 预处理后，任意矩形和只需查 4 个角、两加两减，与框大小无关——这正是 OpenCV cv::integral() 所做的事。拖动下面 4 个坐标框选矩形，即可看到 $O(1)$ 公式实时算出结果，并与朴素的「逐格相加」次数对照。

容斥公式： $sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]$ —— 大矩形减去上、左两条，再把多减的左上角加回来。无论框是 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)$ 取区间；边写边查则采用树状数组 / 线段树，把「实时扫描一段」降为对数级。

回到总览，或重新体验树状数组 / 线段树，把内部机制再走一遍—— 上面每个 case 拆解开来，都是这两页讲过的 update / query。