Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Problem with merge sort tree

Правка en1, от Original_Batman, 2018-06-13 21:18:26

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.

  1. 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.

  2. 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.

Теги merge sort tree, #data structure, #advance data structures, #segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Original_Batman 2018-06-13 21:18:26 1097 Initial revision (published)