高效计算任意时间点未平仓股份数量：基于扫描线与二分查找的优化方案

今天聊一个在金融高频场景中很常见的需求：如何快速计算任意时刻的未平仓股份数量？通过事件点预处理 + 前缀累积 + 二分查找，可以把复杂度从 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) —— 左闭右开。也就是说，在终止事件发生的那个时刻，该订单已经不再活跃，所以减法操作应该在这个时间点生效。

然后，把所有事件按时间戳升序排序，计算时间轴上的累积未平仓股份前缀和。这实际上会形成一个非递减的分段常数函数（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) 和 (t, 1) 区分。
• 生产环境中建议封装成类，支持增量更新，比如流式订单接入时能动态维护。
• C++ 里可以用 std::vector> + std::sort + std::upper_bound 实现完全相同的效果。

这个方法本质上把“区间覆盖求和”问题，转化成了“事件驱动的阶梯函数建模”。它不仅是计算几何里的经典技巧，在日志分析、金融系统中也属于一类非常实用的优化范式。