实现支持 add、cancel、query 的计费引擎；操作顺序到达而时间戳可乱序，尽量降低复杂度。

核心回答

操作按到达顺序执行，但数据索引应按timestamp组织；不能因时间戳较小就把后来到达的操作提前执行，也不能用只适合单调时间的队列直接删除“过期”记录。复杂度优化取决于add、cancel、query的确切语义。

需要先明确三个接口的参数、费用怎样产生、cancel是否追溯撤销，以及query查询余额、时间前缀还是区间账单。这些条件决定应选哈希表、带聚合信息的有序树、树状数组还是区间结构。

先明确四件事

1. add是一笔金额记录，还是一段按费率累计的服务？记录是否有唯一ID？
2. cancel是撤销整笔记录，还是从某个时间停止计费？重复取消与未知ID怎样处理？
3. query只看当前已到达操作的状态，还是要重现某个历史版本？时间边界是否包含端点？
4. 时间戳和值域是否预先已知，能否离线处理，是否需要立即回答每次query？

例如后来收到一笔更早时间的add，会影响之后发出的历史时间范围查询；它不能改变此前已经返回的结果，除非业务另外定义了修订或最终结算机制。

一种明确假设下的数据结构

假设add(id,t,amount)增加单笔金额，cancel(id)立即撤销该笔记录对所有时间查询的贡献，query(T)返回“目前仍有效、且t≤T”的金额总和。下面在这组接口语义下推导实现。

维护两个结构：ID哈希表保存t、金额与有效状态；按时间戳排序的平衡树在节点保存该时间金额及子树金额和。

• add：确认ID规则后，在时间t节点增加amount，沿路径更新子树和，并登记ID。
• cancel：通过ID找到原t和amount，只在第一次有效取消时减去该贡献，再更新状态。不同ID可有相同时间，时间节点保存它们的合计。
• query：沿树查T；当前时间≤T时，累加整个左子树和及当前节点值，再进入右子树，否则进入左子树。

平衡树每次更新或前缀查询O(log m)，m为不同时间戳数；ID定位平均O(1)，总空间O(n+m)。Treap给出期望对数界，AVL/红黑树可给对数最坏界；普通退化BST没有这个保证。二分列表虽然定位快，中间插入仍可能O(n)。

例如先add(A,20,7)，再add(B,5,3)，query(10)为3，query(20)为10；cancel(A)后query(20)为3。到达顺序与按时间筛选是两个独立维度。

其他语义会怎样改变方案

若全部时间戳预先已知，可先排序离散化，用树状数组处理单点增减和前缀和，之后仍按原操作顺序执行；不能为了排序而重排add/cancel/query。预处理通常O(m log m)，操作O(log m)。

若cancel从某时刻停止持续计费，则需记录生效区间与费率，查询可能涉及区间积分；若要历史版本，应考虑事件日志、版本化或可持久化结构。仅查询当前总余额时，一个累计值加ID表就可能平均O(1)，无需有序树。因此，应在明确查询与更新语义后比较复杂度。

参考资料