二叉搜索树通过中序有序性和递归剪枝实现高效区间查询，平均时间复杂度为O(log n)；需增强节点以维护min_val、max_val、sum、count等聚合信息，并注意边界闭合处理与平衡性保障。
二叉搜索树（BST）天然适合区间统计——它不是靠暴力遍历，而是利用有序结构剪枝跳过无关分支，把范围查询从 O(n) 降到平均 O(log n)。关键不在于“能不能查”，而在于“怎么组织、怎么走、怎么聚合”。
区间查询的核心逻辑：中序有序 + 递归剪枝
BST 的中序遍历结果是严格升序的，这意味着任意一个子树，其所有节点值都落在某个连续数值区间内。做范围统计（如求 [L, R] 内元素个数、和、最大值等）时，不需要访问整棵树，只需按以下规则递归判断：
- 若当前子树最大值
- 若当前子树最小值 > R，整个子树全在区间右侧 → 跳过
- 否则，该子树与 [L, R] 有交集 → 进入左右子树继续判断
实际实现中，可在每个节点额外维护 min_val、max_val、sum、count 等聚合字段（即“子树摘要”），让剪枝决策常数时间完成。例如，某节点右子树的 min_val 是 85，而查询区间是 [10, 70]，直接跳过整个右子树，省去大量递归调用。
支持高效聚合的增强型 BST 结构
普通 BST 不带聚合信息，每次范围查询仍需遍历匹配节点。要真正提速，需构建“增强 BST”（Augmented BST）：
- 每个节点存储：自身值 + 左右子树的 sum 和 count（可递推更新）
- 插入/删除时，自底向上回溯更新路径上所有祖先的聚合值
- 查询 [L, R] 区间和时，递归函数返回该子树在区间内的部分和，而非布尔命中标志
例如，统计 [20, 60] 内所有值之和：遇到值为 45 的节点，且其左右子树已知 sum 分别为 32 和 71，则只需判断左右子树是否与 [20, 60] 相交，再累加有效部分 —— 避免逐个加叶子节点。
实战中绕不开的两个关键点
一是边界处理必须严格闭合：BST 的“小于走左、大于走右”约定下，等于值只出现在一个位置。区间 [L, R] 应定义为包含端点，因此比较时用 ≤ 和 ≥，并在命中 L 或 R 时立即计入结果，不终止递归（因同值不会重复出现，无需去重）。
二是退化风险直接影响区间性能：如果树严重失衡（如插入已排序序列），区间查询会退化为链式扫描，失去对数优势。工程中建议在高频写入场景搭配 AVL 或红黑树，或定期重构为平衡形态（如中序遍历后建完全二叉树）。
一个典型应用场景：实时价格区间统计
电商后台需快速响应“当前库存中价格在 ¥99–¥299 的商品总销量是多少”。用增强 BST 存储商品，键为 price，节点值为 sales；每个节点维护子树销量和（subtree_sales）。一次查询平均仅访问 log₂N 个节点，即使百万级商品也能在毫秒内返回。对比线性扫描，性能提升常达百倍以上，且写入新增商品时，聚合更新开销也仅为树高量级。
