本文介绍一种基于事件扫描与二分查找的高效算法，将原始 o(m×n) 时间复杂度优化至 o(n log n + m log n)，适用于高频查询场景下的交易订单生命周期分析。
本文介绍一种基于事件扫描与二分查找的高效算法，将原始 o(m×n) 时间复杂度优化至 o(n log n + m log n)，适用于高频查询场景下的交易订单生命周期分析。
在金融系统或高频交易日志分析中，常需快速回答“某时刻有多少股订单处于活跃状态（即已创建但尚未取消或成交）”这一问题。原始暴力解法对每个查询遍历全部订单判断时间区间包含关系，时间开销大、无法应对大规模数据或实时响应需求。
核心优化思路是
将时间轴上的变化抽象为离散事件
：每个订单的 created_at 是+shares事件，cancelled_or_executed_at 是−shares事件。所有事件按时间排序后，即可构建一个
分段常数函数
——在相邻事件时间点之间，未平仓股份数保持恒定。
具体实现分为三步：
事件提取与合并
：遍历所有订单，生成 (timestamp, delta_shares) 二元组，其中 delta_shares = +shares（创建）或 −shares（结束）；
前缀和扫描
：对事件按时间升序排序后，计算累积和，得到每个关键时间点对应的
当前未平仓总量
；
查询加速
：对每个 query_time，使用 bisect 在已排序的时间点数组中定位其左侧最近的事件位置，直接查表得结果。
以下是完整、健壮的 Python 实现（含边界处理与注释）：
✅
关键注意事项
：
时间边界语义严格遵循 [created_at, cancelled_or_executed_at)，因此 query_time == executed_at 时该订单
不计入
，这通过事件排序中让 −shares 优先于同时间的 +shares 来保障；
若存在大量重复时间戳，建议使用稳定排序并显式控制事件顺序；
本方案天然支持增量更新：新增订单只需插入对应事件并重扫局部前缀和（可进一步用平衡树/线段树优化为动态版本）；
C++ 实现可使用 std::vector> + std::sort + std::upper_bound，逻辑完全一致。
该方法将问题从“对每个查询做全量扫描”升维为“预计算时间轴状态快照 + 对数级随机访问”，是典型“空间换时间”与“离线预处理”的工程实践范例，广泛适用于行情快照、订单簿快照、资源占用监控等时序聚合场景。
from bisect import bisect
def calculate_outstanding_shares(orders, queries):
# Step 1: Extract events (time, delta)
events = []
for order in orders:
order_token, shares, price, side, created_at, executed_at = order
events.append((created_at, shares)) # order becomes live
events.append((executed_at, -shares)) # order ceases to be live
# Step 2: Sort by time; if same time, process exits before entries?
# Note: Since interval is [created, executed), executed_at is exclusive →
# at time t == executed_at, order is no longer live.
# So we want -shares to take effect *at or before* +shares when times equal?
# Actually: for query_time == executed_at → should NOT include this order.
# Thus, sort by time, and for ties: process -shares first to ensure correctness.
events.sort(key=lambda x: (x[0], x[1])) # negative deltas first ensures correct exclusion at boundary
# Step 3: Build timeline of cumulative outstanding shares
timeline = []
total = 0
for time, delta in events:
total += delta
timeline.append((time, total))
# Edge case: if no orders, timeline is empty → default to 0
if not timeline:
return {q: 0 for q in queries}
# Step 4: Answer each query via binary search
result = {}
for q in queries:
# Find rightmost event with time <= q
pos = bisect(timeline, (q, float('inf'))) - 1
if pos < 0:
result[q] = 0 # query time before first event
else:
result[q] = timeline[pos][1]
return result
# Example usage & validation
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))
# Output: {500: 10, 1500: 30, 2500: 45, 3500: 50, 5500: 25}