I read merge sort trees from here (https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial)
understood the build function but I can’t understand the query function.
- Why would you go top to bottom? you’ll meet the “if( x<=l && r<=y )” condition on the root node itself the program will never traverse down the tree. Also for an array of size 10 and a query with a range 2-6 the sorted array can have elements from 6 - 10 and 1 of the original array.
- Also, we can’t search on the merge sort tree as the elements have been shuffled in sorting (ie, the indices of original data and sorted array don’t match), the only possible way on searching on such a tree should be bottom up ie, leaf to tree root because the leaf nodes are pushed in the order of the original data and subsequently we must climb to parent node whenever possible (because minimising number of binary searches is our motive here) climbing can only be done if both the daughter nodes are included in l to r as they are a part of search range and their order doesn’t matter.