Maintains a data structure that supports the following operations:
- inserts an element $$$x$$$ into the set $$$S$$$
- deletes an element $$$x$$$ from the set $$$S$$$
- queries the maximum value of xor for each pair of elements in the set ( $$$\max\limits_{i,j\in S}i\oplus j$$$ )
Can this problem be solved within $$$O(n^2)$$$ better time complexity?
Trie again.
Can you provide a detailed description of your solution? I don't know how to solve it really
How will you use trie for supporting deletion other than probably a potentially working method to do it with an extra $$$\mathcal{O}(\log n)$$$ factor? Inserting is well known enough; deletion sadly not
Can you not just do node.count = node.left.count + node.right.count. When you remove an element, you go down and subtract 1 from the counts.
did you even read the post
Deletion on a trie is well known
but not maintaining the $$$\max(a_i \oplus a_j)$$$ alongside deletion.
You absolutely did not read the post did you.
I read the post. I was just pointing out that you were wrong.
If it's n^2, just maintain a set and then brute force all pairs for every query.
What do you mean I am wrong, your comment hints absolutely nothing towards how to solve the problem. The actually hard part of the problem is maintaining the $$$\max(a_i \oplus a_j)$$$ during deletion, which I implied in "How will you use trie for supporting deletion".
Fuck off, you aren't really understanding the problem even.
What do you think about dealing with the time intervals [tl,tr] in which each number occurs, and then Divide and conquer a segment tree on the timeline? Like some dynamic graph connectivity problem that can be taken offline
I believe that is the method mentioned in the article I linked
you two have great chemistry
I'm saying if its O(n^2) per query, you can brute force all pairs.
If its O(n) per query, it's still possible by maintaining counts and second maxes, sort of like a segment tree beats-like structure on a trie in lognlog(A) per query with n^2 preprocessing.
You need to quit being so hostile when someone corrects you.
try*. learn to spell before commenting next time.
Here is a problem the same as yours: 706D - Vasiliy's Multiset
It's solvable by Trie (I'm new to Trie as well xD)
It's not the same, in the mentioned problem of the main post you want to find $$$\max(a_i \oplus a_j)$$$ where $$$a_i$$$ and $$$a_j$$$ are both elements inside the set.
my bad, I didn't see the difference, thanks to mention it!
I think it's possible just maintain the multiset of max xor by trie for each number and handling insert delete carefull
I think you could solve it offline. for each element in the set mark the time it goes in the set and out of the set now for each element you have interval, you could do same as dynamic connectivity, using a segment tree you could traverse the tree and know what elements where added in this segment and add them to the trie, every time you add an element you take max value of this element and another element in the trie, and each leaf in the tree is a query you can know the max then, and when you leave the node, make the value back to what it was before entering the node. this solution should be $$$O(Q*log(maxVal)*log(Q))$$$
Thank you 111 I never thought of this clever solution but can it be solved online and within a time complexity of $$$O (\log^k n) $$$ ?
If it's offline, then trie + segtree over versions in $$$n \space log n \space log X$$$
Thank you 111 but can it be solved online and within a time complexity of $$$O (\log^k n) $$$ ?
If you necessarily want an online approach, you can do sqrt decomposition and rebuild tries after every query, though the complexity is quite atrocious, even if subquadratic.
Thank you 111 but can it be solved online and within a time complexity of $$$O (\log^k n) $$$
You can try to speed up this heuretically like this: If there is non-zero numbers with the most significant bit (MSB) both 0 and 1, the solution will obviously have MSB = 1, and you can assume that
i's MSB is 0, andj's MSB is 1. (If all the numbers have the same MSB, just ignore this bit and continue to the 2nd MSB.)Now you can imagine, that you are building your solution with
iandjbeing in different subtrees of your trie. Now you try to optimize 2nd MSB of the solution: you check whether in the subtrees ofiandj, continuation of type (0, 1) or (1, 0) is possible. Note that if both types of continuation are present, you must explore all the possibilities (that's why this cannot simply reduce the complexity to $$$O(\log n)$$$). If all continuations ofiandjhave the same bit, just continue to next MSB.Note that you most likely want to do this in BFS order and not DFS order (ie. if at some continuation you see
i = 0110...,j = 1001..., and the next recursion starts fromi = 0001...andj = 1111..., you don't have to continue but exit early).I don't know how to compute the complexity of that but for random data you should roughly halve the size of search size for each bit. And for very dense data it would seem that there are a lot of pairs of the same type (i.e. (0, 0) or (1, 1) continuations) while of different type (i.e. (0, 1) and (1, 0)) are available, so also skipping a lot of entries.
If you implemented this, let me know how it performs :)
Good luck!
Thank you! Much faster than I expected, when $$$Q=2\times 10^5,V=2^{30}-1$$$ it only cost 1 second(but my data isn't strong enough)
You can do it in $$$O(n \cdot \log{n})$$$ offline. you only need rollbacks (in this case you just save maximums along with a trie), and you can add offline deletion.