XORMIN - Editorial

data-structure
editorial
medium
segment-tree
trie
april19

#22

Wouldn’t the merge over all tries be O(n^2) on a tree of the following form?

1--3--5--7 ...
|  |  |   
2  4  6  ...

#23
if(a == NULL)
      return b;
if(b == NULL)
      return a;

This snippet of merge function will tend to give complexity of order O(n) in example given by you.

I think the worst case time complexity may be of order O(n * n^1/2) in the case where root node have n^1/2 children and each children’s subtree have n^1/2 nodes…
Use of compressed trie might have balanced this.


#24

Can someone explain how the author’s solution uses O(N * log N * log C ) space for the persistent data structure ? Also, for a node, why are we excluding it’s child with largest subtree size, while calling update ? I’m guessing both are linked… it would be really helpful if someone could explain this… Thanks


#25

The author’s solution was to apply persistence to each node in the tree and you can do this while traversing the tree in bottom-up fashion. Computing the tries for childrens you can build the trie for the parent. It requires merging and thus merging as explained here is done(small to large trick) .
Thus the merging part takes N * logN thereby making the overall space complexity just
O(N * log N * log C ).


#26

Thanks for the reply… I had already gone through this post on codeforces. For the proof of complexity they just gave a reference to HLD/dsu, without details… I tried deriving it on my own, but I couldn’t… Is there any proof that clearly explains how merging takes N * log N time, in this case space ?