Codercell's blog

Doubt on Trie
By Codercell, history, 10 years ago, In English

Guys , in the below TRIE tutorial in problem 2 , he explains a way to find maximum XOR subarray in a given array.But i find that the method illustrated requires O(n^2) operations as N times he queries the Trie each of which takes linear time.How does the solution pass the time limit. Trie Tutorial

Trie Question

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Querying trie works O(log2(val)) because it's length is log2(val), so overall n * log2(max_ai).

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Fun fact: tries over binary bits of values is actually a segment tree!

Querying the trie is therefore actually just querying a segment tree, O(log_base2(max_value)).

→ Reply