algorithm - 跟踪累加结果，无反操作

Question

我有一个操作 A * A -> A，它是可交换和结合的。这意味着我应用它的顺序并不重要，只要我使用相同的元素即可。不错。

我必须将它应用于值列表。更准确地说，我必须将它用作累积列表值的操作。到目前为止，还不错。

然后我有一系列请求将元素添加到列表中，或从列表中删除它。每次插入或删除后，我都必须返回新列表的新累加值。很简单，对吧？

问题是我没有逆；如果我只知道 a * b 并且告诉我另一个操作数一定是 一个。 (事实上​​ ，甚至没有身份元素)

所以，我唯一明显的选择是在每次删除时再次累积 - 在线性时间内。

我可以做得更好吗？我想了很多。

答案是，我当然可以……如果我真的想要:我需要实现一个自定义二叉树，也许是红/黑二叉树，以获得良好的最坏情况保证。在 value 旁边有一个额外的 cache 存储整个子树的结果。

cache = value * left.cache * right.cache

在每次操作后保持这个不变量；那么根缓存就是结果。

但是，“在保持额外不变性的同时实现自定义 R/B 树”并不是我特别擅长做的事情。好吧，我会这样做，但不会发誓它的正确性。另外，日志前的常量可能很重要。做一件简单的事情(例如跟踪积累)似乎很笨拙。

有没有人看到更好的解决方案？

为了完整性:操作是过滤器的联合。过滤器是一对 (code, mask)，如果 (C 位运算符) (value ^ code) & mask == 0 值“通过过滤器”；也就是说，如果它对应于 mask 中设置的位的位等于 code 中的相应位。因此，联合将掩码或代码不同的位设置为 0(忽略)，并保留相同的位。

感谢任何找到一种方法来利用操作的特定属性来获得比我抽象的一般问题更有效的解决方案的人! ;-)

Answer 1

对于您的具体问题，您可以跟踪每一位 x:

1. 掩码中位 x 被设置为 1 的总次数
2. 掩码中bit x被设置为1且代码的bit x等于0的总次数
3. 掩码中位x置1且代码位x等于1的总次数

有了这 3 个计数(对于每个位)，可以直接计算所有过滤器的并集。

添加或删除过滤器的复杂度为 O(R)(其中 R 是掩码中的位数)。