### Tet's blog

By Tet, history, 3 years ago,

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.

• +269

 » 3 years ago, # | ← Rev. 4 →   +303 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
•  » » 3 years ago, # ^ | ← Rev. 2 →   +33 is this called Shahrezaei segment tree? :P
•  » » » 3 years ago, # ^ |   +45 this is the original version of Sohrabi :)
 » 3 years ago, # |   +81 Lol do you want to add some problems for ptacticing this amazing trick?
 » 3 years ago, # |   +67 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.
 » 3 years ago, # |   +52 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.
 » 3 years ago, # |   +26 Is there anything besides minimum and maximum that this trick can be used with?
 » 3 years ago, # |   +135 Nice trick
•  » » 3 years ago, # ^ |   +148