bit-manipulation - 一系列随机数的按位与(效率)

Question

给定数组中的一系列随机数，例如:147, 95, 254, 78, 66, 120，如何从索引 n 中找到操作数的结果code> 索引 m 时它们被有效地 &ed(按位 &)？

例如:

n = 2 和 m = 5。这意味着您必须 & 数组中从第二个元素 (95) 到第五个元素 (66) 的数字。

除了将它们一个接一个地 & 之外，我不知道该怎么做，但这效率不高。我正在处理的问题有多个查询，这意味着对于一系列随机数(例如上述)，问题可能会多次询问 & 中数字的结果n 元素直到 m 元素，每个查询包含不同的 n 和 m 值。

---

编辑:我试过执行以下操作:将所有数字更改为二进制位并将所有位存储在双端队列中。然后检查给定范围内是否有一位为0，如果有一个0，则该位返回0值。我确实得到了正确答案。但是，它仍然不够有效。 Here是我的代码

Answer 1

这可以通过 k range-sum-queries 来完成，其中 k 是元素的大小(以位为单位):

对于每个位位置，执行范围求和查询。如果结果小于跨度的长度，则该位在结果中为零，否则为一。使用 k 前缀和数组可以很容易地完成这些操作，当然与输入相比，这些数组的存储量相当大。

所以要明确一点，这个想法是为每个元素的只是最低有效位设置一个前缀和数组(并且对其进行的查询计算结果的 lsb)和另一个用于第二位，依此类推，直到 k。

前缀与数组不能以相同的方式使用，例如考虑第一个元素是否为零，但确实工作的单词级替代方案是横向堆。这将只需要一个实际查询(虽然更复杂)，并且只需要大约两倍的输入空间(尽管四舍五入为二的幂)。这需要一个奇特的“双面查询”，您可以从两片叶子以锁步方式向上爬树，并在它们在其 LCA 相遇时停止(此时端点之间的范围已被覆盖，仅此而已)。更多信息 in this other answer .

这两个选项可能只对竞争性编程有用，因为它们有意让朴素的算法在疯狂的大型查询中窒息。