Cumulative bitwise operations

There is impossible to use prefix/cumulative BITWISE-OR array to calculate the Bitwise-or of some random range, you can try with a simple case of 2 elements and verify yourself.

However, there is different approach, which is making use of prefix sum.

Assuming that we are dealing with 32 bit integer, we know that, for the bitwise-or sum from range x to y, the ith bit of the result will be 1 if there exists a number in range (x,y) that has ith bit is 1. So by answering this query repeatedly:

• Is there any number in range (x, y) that has ith bit set to 1?

We can form the answer to the question.

So how to check that in range (x, y), there is at least a number that has bit ith set? we can preprocess and populate the array pre[n][32]which contain the prefix sum of all 32 bit within the array.

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];
       }
   }
}

And, to check if bit i is set form range (x, y) is equalled to check if:

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

Repeat this check 32 times to calculate the final result:

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;

A plain prefix array does not work, because in order to support arbitrary range queries it requires elements to have an inverse relative to the operator, so for example for addition that inverse is negation, for XOR that inverse is the element itself, for bitwise OR there is no inverse.

A binary indexed tree also does not work, for the same reason.

But a sideways heap does work, at the cost of storing about 2*n to 4*n elements (depending on how much is added by rounding up to a power of two), a much smaller expansion than 32*n. This won't make the most exciting use of a sideways heap, but it avoids the problems of an explicitly linked tree: chunky node objects (~32 bytes per node) and pointer chasing. A regular implicit binary tree could be used, but that makes it harder to relate its indexes to indexes in the original array. A sideways heap is like a full binary tree but, notionally, with no root - effectively we do have a root here, namely the single node on the highest level that is stored. Like a regular implicit binary tree a sideways heap is implicitly linked, but the rules are different:

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

Additionally we can compute some other things, such as:

• leftmostLeaf(x) = x - (x & -x) + 1
• rightmostLeaf(x) = x + (x & -x) - 1
• The lowest common ancestor of two nodes, but the formula is a bit large.

Where x & -x can be written as Integer.lowestOneBit(x).

The arithmetic looks obscure, but the result is a structure like this, which you can step through the arithmetic to confirm (source: The Art of Computer Programming volume 4A, bitwise tricks and techniques):

Anyway we can use this structure in the following way:

• store the original elements in the leaves (odd indexes)
• for every even index, store the bitwise OR of its children
• for a range query, compute the OR of elements that represent a range that does not go outside the queried range

For the query, first map the indexes to leaf indexes. For example 1->3 and 3->7. Then, find the lowest common ancestor of the endpoints (or just start at the highest node) and recursively define:

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

So any node that corresponds to a range that is totally covered is used as a whole. Otherwise, if the left or right children are covered at all they must be recursively queried for their contribution, if either of them is not covered then just take zero for that contribution. I am assuming, by the way, that the query is inclusive on both ends, so the range includes both begin and end.

It turns out that rightmostLeaf(left(i)) and leftmostLeaf(right(i)) can be simplified quite a lot, namely to i - (~i & 1) (alternative: (i + 1 & -2) - 1) and i | 1 respectively. This seems awfully asymmetrical though. Under the assumption that i is not a leaf (it won't be in this algorithm, since a leaf is either fully covered or not queried at all), they become i - 1 and i + 1 respectively, much better. Anyway we can use that all the left descendants of a node have a lower index than it, and all right descendants have a higher index.

Written out in Java it could be (not tested):

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;
}

An alternative strategy is starting from the bottom and going up until the two sides meet, while collecting data on the way up. When starting at begin and its parent is to the right of it, the right child of the parent has a higher index than begin so it is part of the queried range - unless the parent was the common ancestor of both upwards "chains". For example (not tested):

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;
}

Building the tree in the first place is not trivial, building it in ascending order of indexes does not work. It can be built level-by-level, starting at the bottom. Higher nodes are touched early (for example for the first layer the pattern is 2, 4, 6, while 4 is in the second layer), but they will be overwritten anyway, it's fine to temporarily leave a non-final value there.

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)];
        }
    }
}