Sparse Table Algorithm Range Minimum Query

In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science such as the lowest common ancestor problem or the longest common prefix problem (LCP).

[sagarcs]

You should maybe stop asking for likes and shares. No one in their good sense will dislike this video. You truly understand the various phases of the algorithm one finds difficulty grasping and try to cover them in meticulous and illustrative examples. You deserve an award for being only one of the kind of Youtube Channel that has a whole lot of algorithm explanation. Awesome Sir!

[Nikita-xkfc]

114k subscribers are very less for u.I haven't seen ny video with this level of explanation.superb xplanation

[jfcahoon]

Just wanted to say thank you for all the work you've put into these videos and explanations. Your work has helped me immensely and I really appreciate it.

[nitinjain]

khatarnak tarike se dhulai karte hai aap algorithms ki...use chupne ki jagah nahi milti.... u r great sir ji

[aayushbaniyal]

thanks for the videos... they were really helpful ... just know that because of you many students didn't got supply in algorithm course

[vineetsharma]

Great Explanation! Your videos are helping dev community a lot.

[ramakrishnachowdary]

Wow, such a clean explanation, Thank You 💙

[anhdungoan]

This video is really useful, thank you very much, some people mistakenly thought the dislike button was a download button :D

[serhiypidkuyko]

Hi Tushar.
Thank you for your video.
I think for your viewers would be useful to explain the main idea of the algorithm with a sparse table.
And this is as following:
any range-interval [u, v] to divide onto two intersecting intervals [u, u+2^k-1] and [v+1-2^k, v] of length 2^k
these two intervals are intersecting because by choice: 2^k<=v-u+1<2^{k+1} ->
then the minimum for the range-interval [u, v] equals the minimum of two numbers - the minimums for the intervals [u, u+2^k-1] and [v+1-2^k, v]
and these two minimums we have in our sparse table.
Here is the code in python:
#
def sparse_table(li):
n=len(li)
t=[]
for i in range(n):
t.append([i])
j=1
while 2**j<n:
for i in range(n-2**j+1):
if
t[i].append(t[i][j-1])
else:
t[i].append(t[i+1][j-1])
j+=1
return t
#
input math
def min_query(li, t, u, v):
k=math.floor(math.log(v-u+1, 2))
if
return li[t[u][k]]
else:
return li[t[v+1-2**k][k]]
#
def test():
li=[4, 6, 1, 5, 7, 3]

s='min for range [{}, {}] equals {}'
m=min_query(li, t, 3, 5)
print(s.format(3, 5, m))
m=min_query(li, t, 0, 5)
print(s.format(0, 5, m))
m=min_query(li, t, 0, 3)
print(s.format(0, 3, m))

[nguyenducvuanh]

Thank you sir! I would have given up on the problem without this video.

[s_cube]

Explanation of pseudo code at the end is what i love most in your videos.. literally it saved hours of my effort for understanding how this algos work.. and all these bcz u put days of effort into building this awesome videos. Such clean and clear explanations with examples. Thank you sooo much!! Hats off to you.
Please keep uploading more. Also if possible put links to some problems related to this algos to practise. Thanks once again!

[Himanshu-edmf]

Important point : if we have to find out sum of elements in range [L, R], then sparse table will give time complexity O(log N) not O(1)

[imyashdeepsharma]

That was very good explanation, cleared some of my doubts ! Thanks Tushar Sir :)

[thesavagetrader]

Thanks sir for your great effort... very simple and easy explanation.

[pritommitchellrodrigues]

Thanks bhai, finally understood how it works. :D

[christy_yinyan]

Thank you so much! always the best!!!!

[AmanGarg]

Hi Tushar. If we were to do point updates at an index, then we would update all those entries at which the index in picture might contribute as a minimum to, right? This would be O(N logN) for N such point update queries. Am I correct in saying this?

[sushmitagoswami]

while doing the range query, why are we moving by k after we find the min in [query_L, K]? Since, we have already calculated for 2^k number of elements?

[ShubhamJoshishubhamjoshi]

Thanks a lot :D could you please add one of LCA By RMQ also.

[AbhishekKumar-zzts]

sweet and simple explanation, keep it up :D