本文介绍一种将时间复杂度从 o(m×n) 降至 o(n log n + m log n) 的高效算法，通过事件点预处理 + 前缀累积 + 二分查找，快速响应多个时间戳查询的未平仓股份总量。
本文介绍一种将时间复杂度从 o(m×n) 降至 o(n log n + m log n) 的高效算法，通过事件点预处理 + 前缀累积 + 二分查找，快速响应多个时间戳查询的未平仓股份总量。
在高频交易、订单簿快照或实时风控等场景中，常需频繁查询某时刻“仍处于活跃状态（即已创建但尚未取消或成交）”的订单所对应的总股份数量。原始暴力解法对每个查询遍历全部订单判断时间区间包含关系，时间复杂度为 O(m×n)，在订单量（n）或查询量（m）较大时性能急剧下降。
更优解法基于扫描线（Sweep Line）思想：将每个订单的生命周期抽象为两个关键事件——
- 起始事件：created_at 时刻，+shares（新增未平仓股份）；
- 终止事件：cancelled_or_executed_at 时刻，−shares（移除未平仓股份）。
注意：因区间定义为 [created_at, cancelled_or_executed_at)（左闭右开），故在 cancelled_or_executed_at 时刻该订单已不活跃，因此终止事件应在此刻“生效”，即减法操作发生在该时间点。
随后，我们将所有事件按时间戳升序排序，并计算时间轴上的累积未平仓股份前缀和，形成一个非递减分段常数函数（step function）。对于任意查询时间 q，只需定位其左侧最近的事件点，即可获得该时刻的实时未平仓总量。
Python 实现如下（使用 bisect 模块实现 O(log n) 查询）：
from bisect import bisect
def calculate_outstanding_shares(orders, queries):
# Step 1: 构建事件列表 (timestamp, delta_shares)
events = []
for order in orders:
_, shares, _, _, created_at, executed_at = order
events.append((created_at, shares))
events.append((executed_at, -shares))
# Step 2: 按时间戳排序（时间相同时，按 delta 排序可确保逻辑一致；此处默认 -shares 在 +shares 后不影响结果）
events.sort(key=lambda x: (x[0], x[1]))
# Step 3: 构造前缀累积数组：[(t0, s0), (t1, s1), ..., (tk, sk)]
# 其中 si 表示在时间 ti（含）之后、ti+1（不含）之前的未平仓总量
cum_shares = []
curr = 0
for t, delta in events:
curr += delta
cum_shares.append((t, curr))
# Step 4: 对每个 query_time，二分查找最后一个 ≤ query_time 的事件点
result = {}
for q in queries:
# bisect 返回插入位置，减1即为最右匹配索引
idx = bisect(cum_shares, (q, float('inf'))) - 1
if idx < 0:
result[q] = 0 # 查询时间早于所有事件
else:
result[q] = cum_shares[idx][1]
return result
# 示例验证
orders = [
[3, 15, 200, True, 2000, 4000],
[1, 10, 100, True, 0, 5000],
[4, 25, 250, False, 2500, 6000],
[2, 20, 150, False, 1000, 3000],
]
queries = [500, 1500, 2500, 3500, 5500]
print(calculate_outstanding_shares(orders, queries))
# 输出：{500: 10, 1500: 30, 2500: 45, 3500: 50, 5500: 25}✅ 关键优势说明：
- 预处理 O(n log n)：仅需一次排序与线性扫描；
- 单次查询 O(log n)：利用 bisect 在有序事件数组中快速定位；
- 空间 O(n)：仅需存储 2n 个事件及其累积值；
- 支持离线批量查询：适用于日终批量快照、回测分析等场景。
⚠️ 注意事项：
- 若存在同一时刻多个事件（如多个订单同时创建或结束），上述排序 key=(t, delta) 可保证先加后减逻辑正确（因 +shares > −shares 数值上成立，但更严谨做法是显式规定：创建事件优先于终止事件，即 (t, 0) vs (t, 1)）；
- 实际生产环境建议封装为类，支持增量更新（如流式订单接入）；
- C++ 中可使用 std::vector<std::pair<int, int>> + std::sort + std::upper_bound 实现同等效果。
该方法本质是将“区间覆盖求和”问题转化为“事件驱动的阶梯函数建模”，是计算几何、日志分析与金融系统中一类经典优化范式。
