Doritos4's blog

Nastya and King Shamans
By Doritos4, history, 6 years ago, In English

codeforces.com/blog/entry/60083

In the editorial for problem E, how does the author descend down the segment tree to find the leftmost maximum element? It hasn’t been explained there.

Edit: I’ve understood how to go down the tree, but I’m unable to convince myself that its complexity is O(logn) per query. Please help.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a common query in segment trees. The order is what matters. You first check your left child. If you found no answer you check the right child. It is easy to see that the first answer you find is the leftmost.

If it is not clear you can check the function qryMax in this code: 39448626

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You want to find the leftmost element that is  > x in the range [L, R].

So, if a certain node's range lies completely outside [L, R] or if the maximum in that range  ≤ x, discard the node.

Otherwise, go to the left subtree. If there's no answer in the left subtree, go to the right subtree.

If you have reached a leaf, then it is the one you want. The leaf is the leftmost such leaf because we have always gone left-first. The leaf is guaranteed to be  > x because we have discarded nodes who's maximum was  ≤ x

You can refer to my editorial here for more details.

→ Reply