数据流与区间问题：概览

典型业务场景

处理随时间变化的数据或需要复杂的区间查询是高性能系统的核心需求：

• 金融交易： “上午 10:00 到下午 2:00 之间的最高股价是多少？” (RMQ - 區間最值查詢)。
• 广告技术： 在数百万个特定时间段内计算广告系列的总消耗。
• 游戏开发： 实时排行榜，玩家的分数每秒都在变化（动态更新）。
• 监控监控： 在滑动窗口中寻找过去 10,000 个请求的中位延迟。
• 物流系统： 确定路线中特定地理分段的总负载。

选型框架：怎么选？

1. 数据是静态的还是动态的？
   • 静态（无更新）： 使用 稀疏表 (Sparse Table) 实现 $O(1)$ 的区间查询。
   • 动态（频繁更新）： 使用 线段树 (Segment Tree) 或 树状数组 (Fenwick Tree)。
2. 查询类型是什么？
   • 区间和： 树状数组 内存最省，实现最简单。
   • 复杂区间操作 (最值/公约数)： 线段树 是万能解法。
3. 是否是持续的流数据？
   • 是： 使用 滑动窗口 (单调队列) 或 对顶堆 来计算中位数等实时指标。

常见算法速览

• 6.1 线段树： 瑞士军刀。支持 $O(\log N)$ 的区间修改和区间查询。
• 6.2 树状数组 (BIT)： 轻量级结构，专攻前缀和与点更新。
• 6.3 稀疏表： 通过预计算，在常数 $O(1)$ 时间内回答区间最值查询。
• 6.4 单调队列： 高效寻找大小为 $K$ 的滑动窗口内的最大/最小值。
• 6.5 对顶堆： 在实时数据流中寻找中位数的标准模式。

选型对比速查表

一句话心法

“区间结构通过少量的预处理和内存，将低效的线性扫描转化为闪电般的对数或常数级查找。”