Hello everyone, nowadays I frequently encounter some very interesting problems on merge sort tree. A few days back I tried with segment tree(with TreeSet in each node). Now TreeSet stores all the elements in sorted order and I merged two nodes with the addAll() operation but I encountered a TLE. I am really curious as of how merge sort tree is implemented in JAVA. As I know C++ has really a nice STL implementation of the function merge() for merging two vectors in sorted order.
What do you need to store on each node, a TreeSet or an ArrayList? If ArrayList, simple merge function can be implemented using two pointers, one for each child, inserting in current node vector in required order.
Similar thing can be done using Iterator for TreeSet with similar complexity.
Have a look for Iterator here.
2 Likes
void combine(int pos1,int pos2,int pos)
{
int l=0,r=0;
while(l<st[pos1].size() && r<st[pos2].size())
{
if(st[pos1][l]<st[pos2][r])
st[pos].pb(st[pos1][l++]);
else
st[pos].pb(st[pos2][r++]);
}
while(l<st[pos1].size()) st[pos].pb(st[pos1][l++]);
while(r<st[pos2].size()) st[pos].pb(st[pos2][r++]);
}
1 Like
Link to problem??
doesnt treeset has an additional complexity of LOGN for accessing elements? Anyways you can merge 2 sorted arrays in O(N)
The recent long challenge which had a very interesting problem PDELIV : CodeChef: Practical coding for everyone and the question I was talking about a TLE, is from a recent ongoing external contest so I don’t want to discuss that problem as of now.
PDELIV needed normal segment trees, merge sort trees werent needed. Anyways you can always write your own merge function. Below I am posting my own merge function so that you can have an idea
Yeah actually I needed to be clear with merging, as two nodes(segment tree) with CHT needed to be merged, I am stucked up as of how to do it efficiently.
1 Like
You dont need to merge in PDELIV. You just loop through all the lines in the range that current node covers and insert them in current nodes hull in sorted order.