二叉搜索树需扩展子树统计信息（如size、sum、min_val/max_val）才能高效支持区间聚合计算，否则暴力遍历退化为O(n)；静态场景可用中序遍历转数组+二分查找实现O(log n)查询。
二叉搜索树（BST）本身不直接支持区间聚合计算，比如求某数值范围内的元素个数、最大值、和或平均值。但它的结构特性——左子树全小、右子树全大、中序遍历有序——为高效实现**范围统计**提供了天然基础。关键在于：不是用原始BST硬算，而是通过扩展节点信息 + 有序遍历策略，把“区间问题”转化为“路径决策 + 子树累加”问题。
为什么原始BST不适合直接做区间聚合？
标准BST只维护父子关系和大小方向，每个节点不知道自己子树里有多少个数、最大最小值是多少、总和多大。每次查一个区间，若暴力遍历所有节点判断是否在范围内，时间复杂度退化为 O(n)，完全失去BST优势。
真正实用的方案是：在插入/删除时同步维护子树元信息，让每次范围查询能快速跳过整棵无关子树。
带子树统计信息的增强型BST
在基础节点上增加字段，例如：
- size：以该节点为根的子树中节点总数
- sum：子树内所有值之和（支持区间求和）
- min_val / max_val：子树最小/最大值（支持区间极值）
这些字段可在插入、删除、旋转（如用于AVL或红黑树）时自底向上更新，开销仅为 O(h)，不影响整体复杂度。
例如，查询“值在 [L, R] 范围内的元素个数”，递归过程如下：
- 当前节点值
- 当前节点值 > R → 只需查左子树
- 当前节点值 ∈ [L, R] → 左子树中满足的部分 + 1 + 右子树中满足的部分
- 若左子树最大值 R，也可跳过
中序遍历 + 二分定位：轻量级替代方案
如果修改原树结构不可行（如仅读取已有BST），可用“中序转数组 + 二分查找”组合：
- 对BST做一次中序遍历，得到升序数组（O(n) 预处理）
- 后续所有区间查询用 lower_bound 和 upper_bound 找边界索引（O(log n) 每次）
- 适合静态或低频更新场景，代码简单、调试友好
例如：数组 arr = [1,3,4,6,7,10,13,14]，查 [5,12] 内元素个数 → lower=6（idx=3）、upper=13（idx=6）→ 个数 = 6−3 = 3。
实际应用中的典型模式
变量范围统计常见于以下场景，BST扩展后能自然支撑：
- 实时风控：统计过去1小时交易金额在 [1000, 5000] 的订单数（按时间戳建BST，值存金额）
- 游戏排行榜：查等级在 [30, 50] 的玩家总战力（BST按等级排序，节点存战力+数量）
- 传感器数据聚合：温度传感器流式写入，快速响应“当前温度在 [22.5℃, 25.8℃] 的设备数”
注意：若数据有时间衰减、滑动窗口等要求，需结合平衡树（如Treap、Splay）或搭配堆/双端队列协同管理生命周期。
