CODEWITHSUNDEEP
c++algorithmtree
ChuNan
ChuNan

Reputation: 1141

Binary index tree applied to bitwise AND

I was wondering whether binary index tree(BIT) can be used to implement the range query with bitwise AND (instead of the common use of range sum)?

Here is my code for the update part:

memset(BIT,1<<20-1,sizeof(BIT));
void update(int idx){
    while(idx<=n){
        BIT[idx] &= a[idx];
        idx += idx&(-idx);
    }
}

Can someone show me whether it is possible to write the code for query part? As I know, the range sum query is something like:

int query(int idx){
    int res = 0;
    while (idx){
        res += BIT[idx];
        idx -= idx&(-idx);
    }
    return res;
}

And to query the sum of [a,b], the answer is query(b)-query(a-1). How can I modify this to a bitwise AND range query?

Upvotes: 1

Views: 648

Answers (2)

user555045
user555045

Reputation: 64903

To expand on user2040251's answer, in case you were interested, you could do it with several Binary Indexed Trees.

Consider a single bit. If and only if the sum in a range is equal to the size of the range, the AND over that range will be 1 (otherwise 0, because at least one thing in that range must be 0).

So you'd need one BIT per bit, and two queries per bit, so in all it doesn't work out that well, but it does work.

Upvotes: 1

kraskevich
kraskevich

Reputation: 18566

It is not possible(at least using only one BIT). The reason is simple: if you know the bitwise AND for prefix a - 1 and prefix b, it is not possible to uniquely determine the bitwise AND for [a, b] range. For example, if query(0) is 1 and query(1) is 1, the answer for query(1, 1)(that is, an element with index 1) can be any number which is not divisible by 2.

I would suggest using a segment tree instead.

Upvotes: 1

Related Questions