给定一个数组中的一系列随机数,例如:147, 95, 254, 78, 66, 120,当它们(按位和)有效时,如何从索引n到索引找到操作数的结果？m&
例如:
n = 2和m = 5.这意味着您必须&从第二个元素(95)到第五个元素()的数组中的数字66.
我不知道除了&一个接一个之外如何,但这并不高效.我正在使用的问题有多个查询,这意味着对于一系列随机数(例如上面的),问题可能会多次询问元素中&数字的结果,n直到m每个查询包含不同值的元素中n和m.
编辑:我尝试过以下操作:将所有数字更改为二进制位并将所有位存储在deques中.然后,检查给定范围中的一个位是否为0,如果有一个0,则所述位返回0值.我确实得到了正确的答案.但是,它仍然不够有效.这是我的代码
它可以使用k range-sum-queries来完成,其中k是以位为单位的元素的大小:
对于每个位位置,执行范围求和查询.如果结果小于跨度的长度,则结果中该位为零,否则为1.使用k前缀和数组可以很容易地完成这些操作,但是当然这些与输入相比存储起来相当大.
所以要明确的是,有一个前缀和数组只用于每个元素的最低有效位(并且在它上面执行的查询计算结果的lsb),而另一个只用于第二个位,并且等等,最多k.
前缀-AND阵列不能以相同的方式被使用,例如考虑如果第一元素是零,但一个词级的替代方案,做的工作是一个侧向堆.这将只需要一个实际查询(虽然这更复杂),并且只有输入空间的两倍(尽管四舍五入为2的幂).这需要一个花哨的"双面查询",你从锁定步骤的两个叶子上升到树上,当他们在LCA会面时停止(此时端点之间的范围被覆盖,仅此而已).其他答案中的更多信息.
这两个选项可能只对竞争性编程有用,因为他们故意让天真的算法在疯狂的大型查询上窒息.