累积按位运算

Question

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

然后你计算一个前缀/累积BITWISE-OR数组P = [x, x | y, x | y | z, ... ]

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

我知道它在累积和中起作用以获得一个范围内的总和，但我不确定是否有位操作。

编辑：重复在A允许，所以A = [1, 1, 2, 2, 2, 2, 3]是一种可能性。

Answer 1

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

但是，有不同的方法，即利用前缀和。

假设我们正在处理32位整数，我们知道，对于从x到y的按位或求和，如果在范围（x，y）中存在具有ith的数字，则结果的ith位将为1 bit是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;

Answer 2

Pham Trungs的答案显然是如果你有内存空间的话，因为它在恒定的时间内运行。如果数组很大，并且你不能创建多个相同大小的额外数组，我建议这样一个简单的方案：

预处理阵列A并计算例如块的元素的按位OR。一千个元素，并将它们存储在数组B中。这个数组当然要小一千倍。然后，在执行查找时，您可以使用数组B执行大部分范围，并且查找速度应该快一千倍。

您也可以通过几个步骤完成此操作，例如A中每百个元素的数组B，B中每百个元素的数组C，依此类推。

为了选择最佳的块大小或大小，有助于对要查找的范围进行统计分析，或者至少对一般情况有所了解。

Answer 3

普通前缀数组不起作用，因为为了支持任意范围查询，它需要元素相对于运算符具有反转，因此例如，对于加法，反函数是否定，对于XOR，反函数是元素本身，对于按位OR没有逆。

出于同样的原因，二进制索引树也不起作用。

但是横向堆确实起作用，代价是存储大约2 * n到4 * n个元素（取决于通过舍入到2的幂来增加多少），​​比32 * n小得多的扩展。这不会使横向堆最令人兴奋的使用，但它避免了显式链接树的问题：粗节点对象（每个节点约32个字节）和指针追逐。可以使用常规隐式二叉树，但这使得将其索引与原始数组中的索引相关联变得更加困难。横向堆就像一个完整的二叉树，但从概念上讲，没有根 - 实际上我们在这里有一个根，即存储在最高级别的单个节点。像常规的隐式二叉树一样，侧向堆是隐式链接的，但规则是不同的：

• left(x) = x - ((x & -x) >> 1)
• right(x) = x + ((x & -x) >> 1)
• parent(x) = (x & (x - 1)) | ((x & -x) << 1)

此外，我们还可以计算其他一些东西，例如：

• leftmostLeaf(x) = x - (x & -x) + 1
• rightmostLeaf(x) = x + (x & -x) - 1
• 两个节点的最低共同祖先，但公式有点大。

x & -x可以写成Integer.lowestOneBit(x)。

算术看起来很模糊，但结果是这样的结构，你可以通过算术来确认（来源：计算机程序设计的第4A卷，按位技巧和技巧）：

无论如何，我们可以通过以下方式使用此结构：

• 将原始元素存储在叶子中（奇数索引）
• 对于每个偶数索引，存储其子项的按位OR
• 对于范围查询，计算表示不超出查询范围的范围的元素的OR

对于查询，首先将索引映射到叶索引。例如1-> 3和3-> 7。然后，找到端点的最低共同祖先（或者从最高节点开始）并递归地定义：

rangeOR(i, begin, end):
    if leftmostLeaf(i) >= begin and rightmostLeaf(i) <= end
        return data[i]
    L = 0
    R = 0
    if rightmostLeaf(left(i)) >= begin
        L = rangeOR(left(i), begin, end)
    if leftmostLeaf(right(i)) <= end
        R = rangeOR(right(i), begin, end)
    return L | R

因此，对应于完全覆盖范围的任何节点都将作为一个整体使用。否则，如果完全覆盖了左或右儿童，则必须递归地查询他们的贡献，如果其中任何一个未被覆盖，那么只需为该贡献取零。顺便说一下，我假设查询在两端都是包含的，所以范围包括begin和end。

事实证明，rightmostLeaf(left(i))和leftmostLeaf(right(i))可以简化很多，分别是i - (~i & 1)（替代：(i + 1 & -2) - 1）和i | 1。这看起来非常不对称。假设i不是叶子（它不会在这个算法中，因为叶子完全被覆盖或根本没有被查询），它们分别成为i - 1和i + 1，好得多。无论如何，我们可以使用节点的所有左后代具有比它更低的索引，并且所有正确的后代具有更高的索引。

用Java编写它可能（未经测试）：

int[] data;

public int rangeOR(int begin, int end) {
    return rangeOR(data.length >> 1, 2 * begin + 1, 2 * end + 1);
}

private int rangeOR(int i, int begin, int end) {
    // if this node is fully covered by [begin .. end], return its value
    int leftmostLeaf = i - (i & -i) + 1;
    int rightmostLeaf = i + (i & -i) - 1;
    if (leftmostLeaf >= begin && rightmostLeaf <= end)
        return data[i];

    int L = 0, R = 0;
    // if the left subtree contains the begin, query it
    if (begin < i)
        L = rangeOR(i - (Integer.lowestOneBit(i) >> 1), begin, end);
    // if the right subtree contains the end, query it
    if (end > i)
        R = rangeOR(i + (Integer.lowestOneBit(i) >> 1), begin, end);
    return L | R;
}

另一种策略是从底部开始直到双方会面，同时收集数据。当从begin开始并且其父项位于其右侧时，父项的正确子项具有比begin更高的索引，因此它是查询范围的一部分 - 除非父项是两个向上“链”的共同祖先。例如（未测试）：

public int rangeOR(int begin, int end) {
    int i = begin * 2 + 1;
    int j = end * 2 + 1;
    int total = data[i];
    // this condition is only to handle the case that begin == end,
    // otherwise the loop exit is the `break`
    while (i != j) {
        int x = (i & (i - 1)) | (Integer.lowestOneBit(i) << 1);
        int y = (j & (j - 1)) | (Integer.lowestOneBit(j) << 1);
        // found the common ancestor, so done
        if (x == y) break;
        // if the low chain took a right turn, the right child is part of the range
        if (i < x)
            total |= data[x + (Integer.lowestOneBit(x) >> 1)];
        // if the high chain took a left turn, the left child is part of the range
        if (j > y)
            total |= data[y - (Integer.lowestOneBit(y) >> 1)];
        i = x;
        j = y;
    }
    return total;
}

---

首先构建树并不简单，按索引的升序构建它是行不通的。它可以从底层开始逐级构建。早期触摸较高的节点（例如，第一层图案为2, 4, 6，而4位于第二层），但无论如何它们都会被覆盖，暂时在那里暂时留下非最终值。

public BitwiseORRangeTree(int[] input) {
    // round length up to a power of two, then double it
    int len = input.length - 1;
    len |= len >> 1;
    len |= len >> 2;
    len |= len >> 4;
    len |= len >> 8;
    len |= len >> 16;
    len = (len + 1) * 2;

    this.data = new int[len];

    // copy input data to leafs, odd indexes
    for (int i = 0; i < input.length; i++)
        this.data[i * 2 + 1] = input[i];

    // build higher levels of the tree, level by level
    for (int step = 2; step < len; step *= 2) {
        for (int i = step; i < this.data.length; i += step) {
            this.data[i] = this.data[i - (step >> 1)] | this.data[i + (step >> 1)];
        }
    }
}