Tet's blog

By Tet, history, 7 months ago, In English

First of all this "Trick" is just for fun and it's actually slower than the normal implementation of RMQ with segment trees so do not use it if the time limit is tight.

I did some research and couldn't find any similar blog but don't hesitate to inform me if this has been mentioned before, I'll delete this blog. So let's start!

Assume you have to perform two types of queries on an array:

  1. Find a minimal ( or maximal ) element in a range.
  2. Increase the elements in a range by a given value.

There are a lot of ways to do this but let's assume that you will code a segment tree with three basic functions:

  1. A build function.
  2. An add function which increases the elements in a given range by a given value.
  3. A get function to find a minimal element in a given range.

Now this "Trick" is about getting rid of the get function ( or at least making it shorter ), assume you want to find a minimal element in a given range $$$[l, r]$$$, we all know that the one of the minimal elements in the whole array is stored in the root node of the segment tree, let's take advantage of that!

By simply adding a big enough $$$\infty$$$ to segments $$$[1, l-1]$$$ and $$$[r+1, n]$$$ we will ensure that the value stored in the root node is actually a minimal element in the range $$$[l, r]$$$. ( don't forget to undo the adding operation after answering the query! )

Additionally adding $$$\infty$$$ to a segment can also be interpreted as deleting that segment which is worth mentioning.

Thanks to Mehrdad_Sohrabi for inventing this "Trick" which he refers to by the name Sohrabi segment tree.

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

»
7 months ago, # |
Rev. 4   Vote: I like it +303 Vote: I do not like it

instead of doing 4 add operations ( 2 on a prefix and 2 on a suffix ) you can just subtract $$$\infty$$$ from the segment $$$[l, r]$$$ which will cost 2 add oprations

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it

    is this called Shahrezaei segment tree? :P

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      this is the original version of Sohrabi :)

»
6 months ago, # |
  Vote: I like it +81 Vote: I do not like it

Lol do you want to add some problems for ptacticing this amazing trick?

»
6 months ago, # |
  Vote: I like it +67 Vote: I do not like it

That is a really cool way to code segment trees. I usually don't use build function in segment trees except if I need to build a lot of nodes at the start and updates amount is less than amount of building of nodes and timelimit is strict. So basically, segment tree is transformed into just 1 function which is add.

»
6 months ago, # |
  Vote: I like it +52 Vote: I do not like it

You can also similarly count the conditional minimum outside the paths in the HLD by simply making an infinity on the path, and take the minimum in the subtree. which is also funny.

»
6 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Is there anything besides minimum and maximum that this trick can be used with?

»
6 months ago, # |
  Vote: I like it +135 Vote: I do not like it

Nice trick