跟踪累加结果，无反运算
Keep track of the result of accumulation for operation without inverse
我有一个操作 A * A -> A，它是可交换和结合的。这意味着我应用它的顺序并不重要，只要我使用相同的元素即可。不错
我必须将它应用于值列表。更准确地说，我必须将它用作累积列表值的操作。到目前为止，还不错。
然后我收到一系列请求，要求将元素添加到列表中，或将其从列表中删除。每次插入或删除后，我都必须 return 新列表的新累加值。简单吧？
问题是我没有逆；如果我只知道 a * b 并告诉我另一个操作数一定是 a，那么没有操作 '/' 能够删除 b。 （事实上 ，甚至没有身份元素）
所以，我唯一明显的选择是在每次删除时再次累积 - 在线性时间内。
我可以做得更好吗？我想了很多。
答案是，我当然可以...如果我真的想要：我需要实现一个自定义二叉树，也许 red/black 一个有良好的最坏情况保证的二叉树。在 value 旁边有一个额外的 cache 存储整个子树的结果。
cache = value * left.cache * right.cache
在每次操作后保持这个不变量；那么根缓存就是结果。
但是，"implement a custom R/B tree while maintaining an additional invariant" 并不是我特别擅长做的事情。好吧，我会这样做，但不会发誓它的正确性。另外，日志前的常量可能很重要。做一个简单的事情，比如跟踪积累，似乎很笨重。
有没有人看到更好的解决方案？
为了完整性：操作是过滤器的并集。过滤器是一对 (code, mask) 和一个值 "passes the filter" if (C bitwise operators) (value ^ code) & mask == 0;也就是说，如果它对应于 mask 中设置的位的位等于 code 中对应的位。因此，联合将掩码或代码不同的位设置为 0（忽略），并保留相同的位。
感谢任何找到一种方法来利用操作的特定属性来获得比我抽象的一般问题更有效的解决方案的人！ ;-)
对于您的具体问题，您可以跟踪每个位 x:
- 掩码中位 x 设置为 1 的总次数
- mask中bit x被设置为1且code的bit x等于0的总次数
- mask中bit x设置为1且code的bit x等于1的总次数
有了这 3 个计数（对于每个位），可以直接计算所有过滤器的并集。
添加或删除过滤器的复杂度为 O(R)（其中 R 是掩码中的位数）。
我有一个操作 A * A -> A，它是可交换和结合的。这意味着我应用它的顺序并不重要，只要我使用相同的元素即可。不错
我必须将它应用于值列表。更准确地说，我必须将它用作累积列表值的操作。到目前为止，还不错。
然后我收到一系列请求，要求将元素添加到列表中，或将其从列表中删除。每次插入或删除后，我都必须 return 新列表的新累加值。简单吧？
问题是我没有逆；如果我只知道 a * b 并告诉我另一个操作数一定是 a，那么没有操作 '/' 能够删除 b。 （事实上 ，甚至没有身份元素）
所以，我唯一明显的选择是在每次删除时再次累积 - 在线性时间内。
我可以做得更好吗？我想了很多。
答案是，我当然可以...如果我真的想要：我需要实现一个自定义二叉树，也许 red/black 一个有良好的最坏情况保证的二叉树。在 value 旁边有一个额外的 cache 存储整个子树的结果。
cache = value * left.cache * right.cache
在每次操作后保持这个不变量；那么根缓存就是结果。
但是，"implement a custom R/B tree while maintaining an additional invariant" 并不是我特别擅长做的事情。好吧，我会这样做，但不会发誓它的正确性。另外，日志前的常量可能很重要。做一个简单的事情，比如跟踪积累，似乎很笨重。
有没有人看到更好的解决方案？
为了完整性：操作是过滤器的并集。过滤器是一对 (code, mask) 和一个值 "passes the filter" if (C bitwise operators) (value ^ code) & mask == 0;也就是说，如果它对应于 mask 中设置的位的位等于 code 中对应的位。因此，联合将掩码或代码不同的位设置为 0（忽略），并保留相同的位。
感谢任何找到一种方法来利用操作的特定属性来获得比我抽象的一般问题更有效的解决方案的人！ ;-)
对于您的具体问题，您可以跟踪每个位 x:
- 掩码中位 x 设置为 1 的总次数
- mask中bit x被设置为1且code的bit x等于0的总次数
- mask中bit x设置为1且code的bit x等于1的总次数
有了这 3 个计数（对于每个位），可以直接计算所有过滤器的并集。
添加或删除过滤器的复杂度为 O(R)（其中 R 是掩码中的位数）。