You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem with merge sort tree

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.

asked 13 Jun, 13:51

gintoki_sakata's gravatar image

2★gintoki_sakata
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,669
×1,184
×834
×686
×209
×74
×65
×28

question asked: 13 Jun, 13:51

question was seen: 107 times

last updated: 13 Jun, 13:51