Nineshadow

What is the point of this?

I ask because I'm having trouble figuring out why you want to do a bitwise operation (especially a XOR function), then compare the result with a range of values.

I have a multiset-like data structure on which I need to do 3 operations:

• insert(x) - pretty obvious
• delete(i) - delete the i-th value inserted
• query(a,b) - count how many numbers x there are in the multiset such that x xor a <= b

Of course, it's very simple to implement the query operation in O(n), but that isn't fast enough. I need to get it down to O(logn) or something along those lines.

I'm just not sure if a <= b implies a xor c <= b xor c. If this were true, then it should bring things down to ~O(logn). I do a binary search for the value in a sorted vector and that's pretty much it.

Well I've never had a reason to use a multiset so I'm certainly no expert, but I believe the only way to get O(logn) for count would be if you could transform (y xor x) <= k into some form like y <= (k op x) which I'm not sure is possible for xor then do an upper_bound(k op x). 

@fizzlesticks Well, it's not exactly an std::multiset or something like that. It's just conceptually like that : there can be more than one number with the same value in the data structure.

I think it's obvious I need to implement some kind of binary tree here. It's just that I don't think it's one that's common, it's probably used just for this purpose.

Here's what I'm thinking:

Let's scale down the problem from a multi-bit xor (with integers), to a simple xor with booleans. 

y xor x <= k means that, for each bit in y,x,k, which should fit in 32 bits so let's just use that, the value of y xor x must be smaller or equal than k, where k represents the i-th bit in the number. That's pretty much the definition of bitwise xor, but I needed to emphasise this. If I can store the number of elements with specific bits in specific positions, that should do it.

So let's try it.

The node structure should look something like this :
 

struct node{
	int tot;
	node *one, *zero;
	node(...){...}
}

But how should I construct this tree?

Well, let's say I'm considering i-th bit in the number that's to be inserted.

If the bit is 1, the I go further down the tree to the one child.. If it's 0, then I go down to the zero child. Whichever child I'm at, I increment the tot field. Then I recursively insert from that child, considering the bit i-1.

Removing the i-th inserted number is pretty simple. I hold a vector of the numbers inserted. I get the i-th inserted number from there, then I delete that number from the tree. This should be pretty much the same as the insertion procedure, but decrementing instead of incrementing.

But what about the query?

We need to compare, bit by bit, the value of y xor x to k.

Again, let's say we are considering the i-th bit. We need to select the numbers which respect our condition.

If I visit the one child, then I'll be considering numbers with the bit i equal to 1. Thus, I check if 1 xor x <= k. If it's true, then I recursively query on that child, considering the bit i-1.

If I visit the zero child, then I'll be considering numbers with the bit i equal to 0. I check if 0 xor x <= k, and yada yada yada.

The query is over when I'm at the bottom of the tree, where there are no more children to visit. When that happens, I add whatever I have in the tot field to the solution.

I just got this out of my head now, time to implement it and see if it works. 

I'm not sure what the heck happened to the formatting in the previous post, but whatever.