Input:I am provided with x and y.

x is a 32 bit non negative integer and y is some node-id of the tree.

So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie.

Now here is the extra condition:

I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum. How can we find this out efficiently? Preferably in O(log n).

  • 1
    $\begingroup$ It seems from your edit that you've ended up with two accounts. You can use the "contact us" link at the bottom of the page to ask the site admins to merge them for you. Then you'll be able to edit and comment on your own posts. $\endgroup$ – David Richerby May 13 '17 at 12:48
  • $\begingroup$ You mention "tree (DAG)". Which is it? Is it a tree? Or a DAG? When you say "path", do you mean a path in that tree, or a path in the trie? When you say O(log n), what is n? $\endgroup$ – D.W. May 14 '17 at 1:46
  • $\begingroup$ Possibly useful: en.wikipedia.org/wiki/Heavy_path_decomposition $\endgroup$ – D.W. May 14 '17 at 1:50
  • $\begingroup$ cs.stackexchange.com/q/75361/755 $\endgroup$ – D.W. May 14 '17 at 5:22
  • $\begingroup$ stackoverflow.com/q/43953438/781723 $\endgroup$ – D.W. May 14 '17 at 5:28

You can simply use persistent tries.

Let $T[x]$ denote a trie containing all keys in the path from root to $x$, assume $y$ is a child of $x$, $T[y]$ can be constructed in $O(\log U)$ time from $T[x]$, where $U=2^{32}$. This is trivial even if you use normal tries; but the key point is "persistent" data structures enable you to store all $T[\cdot]$ at the same time. As an intuition, notice that when we construct $T[y]$ from $T[x]$, only $O(\log U)$ nodes in $T[x]$ changes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.