可在o(log n)时间内完成任意时间区间交易流水求和，通过前缀和数组加二分查找实现：先构建时间戳升序数组与金额前缀和数组，再用bisect_left定位起始下标、bisect_right定位结束下标+1，最后以前缀和差值计算区间和。
直接用前缀和数组 + 二分查找（不是“二进制循环检索”，这是常见误称），可在 O(log n) 时间内完成任意时间区间的交易流水求和，轻松支撑毫秒级响应——前提是数据按时间有序且已预处理。
前缀和数组：让区间求和变成两次查表
前缀和本质是把「从开头到每个位置的累计和」提前算好。假设交易流水按时间升序存储在数组 txs[] 中，每条记录含 timestamp 和 amount，先提取出时间戳数组 ts[] 和金额前缀和数组 prefix[]：
- prefix[0] = 0
- prefix[i] = prefix[i-1] + txs[i-1].amount（i 从 1 开始）
- 这样区间 [L, R]（闭区间，按原始索引）的和就是 prefix[R+1] - prefix[L]
二分查找定位时间边界：关键在找第一个 ≥ start 和第一个 > end
用户查「2024-03-01 10:00 到 2024-03-01 10:59」的总和，需快速定位该时间范围内首条和末条记录的下标：
- 用 lower_bound(ts, start) 找第一个时间戳 ≥ 起始时间的位置 left_idx
- 用 upper_bound(ts, end) 找第一个时间戳 > 结束时间的位置 right_idx
- 有效区间就是 [left_idx, right_idx - 1]，对应前缀和差值为 prefix[right_idx] - prefix[left_idx]
实战优化要点：别卡在细节上
真实场景中，毫秒级响应不只靠算法，还依赖以下实践：
- 数据必须按时间严格升序入库，并建立索引；若用数据库，可直接用 WHERE ts BETWEEN ? AND ? + 聚合，现代 OLAP 引擎（如 ClickHouse、Doris）对此已高度优化
- 纯内存计算时，用 std::lower_bound（C++）、bisect_left（Python）等标准库函数，避免手写二分出错
- 若查询极频繁且时间范围固定（如每小时汇总），可预生成滚动窗口前缀和，进一步降为 O(1)
- 注意时间精度对齐：数据库存的是秒还是毫秒？查询参数是否转成同精度再比较？微小偏差会导致边界错位
一个最小可行代码片段（Python）
假设有百万级已排序时间戳和金额：
import bisect <p>ts = [1672531200, 1672531260, 1672531320, ...] # Unix 时间戳，升序 amounts = [120.5, 88.0, 205.3, ...] prefix = [0] for a in amounts: prefix.append(prefix[-1] + a)</p><p>def sum_in_range(start_ts: int, end_ts: int) -> float: left = bisect.bisect_left(ts, start_ts) right = bisect.bisect_right(ts, end_ts) # 等价于 bisect_upper return prefix[right] - prefix[left] </p>
单次调用耗时通常低于 0.1ms（百万数据量级，现代 CPU）。
