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:
- Find a minimal ( or maximal ) element in a range.
- 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:
- A build function.
- An add function which increases the elements in a given range by a given value.
- 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.
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
is this called Shahrezaei segment tree? :P
this is the original version of Sohrabi :)
Lol do you want to add some problems for ptacticing this amazing trick?
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.
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.
Is there anything besides minimum and maximum that this trick can be used with?
Nice trick