我想代表我系统中某个元素在未来的预测状态。元素可以处于状态S1或S2. S1 预测是形式的非重叠间隔，<t_start, t_end>其中t_s 是未来的相对时间。没有S1区间意味着状态是S2且仅S1曾经做过预测。主要操作是添加预测间隔和查询任意未来时间的状态。状态查询将比查询更频繁地发生几个数量级。可以在有限范围内的任何时间以相对于现有间隔的任何顺序添加间隔。另一个重要的操作是时间的进展，这意味着预测越来越接近并最终进入可以被遗忘的过去。预测可能很少被删除，但这不是必需的。时间的基础模型可以是连续的，也可以离散为整数时间步长。
我已经使用链表实现了这一点，其中链表中的位置表示时间（使用离散为整数的时间），节点内容是S1or S2。这非常适合随着时间的推移进行更新（您只需删除第一个节点），并且查询速度相当快（与未来时间步长成线性关系）。但是，因为您要枚举所有可能的时间片，所以在添加预测方面有点难看，并且随着时间范围或时间片精度的增加，它的扩展性很差。因此，我正在寻找一种替代方法（例如，以某种方式基于间隔）。