A funny "Trick" for coding RMQ with segment tree

Правка en4, от Tet, 2021-03-14 11:41:17

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Tet 2021-03-14 11:41:17 5 Tiny change: '14] for innovating this ' -> '14] for inventing this '
en3 Английский Tet 2021-03-14 11:29:33 16
en2 Английский Tet 2021-03-14 11:24:00 105
en1 Английский Tet 2021-03-14 11:19:57 1611 Initial revision (published)