This is a question of JAN15 long. If the value of x is negative(for elements inside array) then can it be done by using trie as given in the editorial? What changes are required in the existing trie with constraint x>=1.
Yes but the implementation gets trickier. We need to check all 32 bits because of the sign bit and negative numbers.
Insert and delete are the same, inserting or deleting all 32 bits of the numbers.
For the xor query, we need to be careful with the sign bit. We want to follow the trie so that the sign bit is zero (positive) instead of one (negative). Then it is the same because in the two’s complement the larger negative numbers also have the most significant bits set to 1.
For the rank and kth number, we need again to be careful of the sign bit as the 1 bit contains smaller numbers than the 0 bit. Then it is the same.
1 Like
My solution was that of a persistent segment tree. I know you asked for tries specifically, but in case anyone wants to try it, here is a possible solution using persistent segment tree.
Let us say, -500000 <= x <= 500000.
Form two separate trees and of course execute queries on them separately. For the positive inputs proceed as you have, for the negative inputs make them positive and add them to the other (negative) tree. For the “negative tree” you will also need to modify your functions so that they execute all queries in reverse, so it will find kth largest number, numbers > k and so on.
For the kth smallest query first check if k can be in negative tree (just check the total numbers in tree from the root node). Similarly for the less than k query if k is in the positive tree add to your answer the number of values in the negative tree and so on. For the XOR queries I think we can just execute a query on positive tree (unless it is empty, in which case you find an XOR value from the negative tree such that you get a minimal value).
Hope it makes sense and I did not make any mistakes. 