java - 累积位运算

Question

假设您有一个数组 A = [x, y, z, ...]

然后计算前缀/累积按位或数组 P = [x, x |是, × |是 | z, ... ]

如果我想找到索引 1 和索引 6 之间的元素的按位或，我该如何使用这个预先计算的 P数组？可能吗？

我知道它适用于累积和以获取范围内的总和，但我不确定位运算。

编辑:A 允许重复，所以 A = [1, 1, 2, 2, 2, 2, 3]是有可能的。

Answer 1

无法使用前缀/累加 BITWISE-OR 数组来计算某个随机范围的 Bitwise-or，您可以尝试使用 2 个元素的简单情况并自行验证。

但是，还有一种不同的方法，就是利用前缀和。

假设我们正在处理 32 位整数，我们知道，对于范围 x 到 y 的按位或求和，如果存在数字，则结果的第 ith<​​ 位将为 1在具有 ith<​​ 位的范围 (x,y) 中是 1。所以通过重复回答这个查询:

• 范围 (x, y) 中是否有任何数字的 ith<​​ 位设置为 1？

我们可以形成问题的答案。

那么如何检查在 (x, y) 范围内，至少有一个数字设置了 ith<​​ 位？我们可以预处理并填充数组 pre[n][32]，其中包含数组中所有 32 位的前缀和。

for(int i = 0; i < n; i++){
   for(int j = 0; j < 32; j++){
       //check if bit i is set for arr[i]
       if((arr[i] && (1 << j)) != 0){
           pre[i][j] = 1;
       }
       if( i > 0) {
           pre[i][j] += pre[i - 1][j];
       }
   }
}

并且，要检查位 i 是否设置为范围 (x, y) 等于检查是否:

pre[y][i] - pre[x - 1][i] > 0

重复此检查 32 次以计算最终结果:

int result = 0;
for (int i = 0; i < 32; i++){
   if((pre[y][i] - (i > 0 ? pre[x - 1][i] : 0)) > 0){
       result |= (1 << i);
   }
}
return result;