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 UA-cam Channel that has a whole lot of algorithm explanation. Awesome Sir!
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.
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
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!
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?
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?
The time complexity to query RMQ Sparse Table in your implementation is log*(n) (not to be confused with log(n), log*(n) is iterated logarithm) which can be reduced to O(1) by choosing 2 [L,R] values such that they cover all the nodes. Read this for more www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)
Hi tushar! what is the logic behind putting index of minimum numbers in table , you could have directly put the minimum value direct in the table. BTW nice video as always.
Correct me If I'm wrong according to the sparse table being taught when i=4, j=0 in the first column, j will be 6 and i will be 7 and the min of both is 6 so the index of the 6 which is 1 should be returned right?
Okay.. Got it.. The application of RMQ demands the storage of indices.. Because, usually, the minimum value is not just "Needed", it can also be updated.
@@madankumarrajan1028 Can you elaborate ? From my understanding, the heap construction algorithm time complexity is not very straight-forward to understand. Also, segment tree should be O(nlogn) according to me, since we use divide and conquer and then sum (in case of Range sum queries) the two child node values.
![Lp. Сердце Вселенной #1 НАЧАЛО ПУТЕШЕСТВИЯ [Новый сезон] • Майнкрафт](http://i.ytimg.com/vi/380Q7gLWGvk/mqdefault.jpg)
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 UA-cam Channel that has a whole lot of algorithm explanation. Awesome Sir!
114k subscribers are very less for u.I haven't seen ny video with this level of explanation.superb xplanation
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.
khatarnak tarike se dhulai karte hai aap algorithms ki...use chupne ki jagah nahi milti.... u r great sir ji
Wow , such a clean explanation , Thank You 💙
I love this, great work sir
thanks for the videos... they were really helpful ... just know that because of you many students didn't got supply in algorithm course
Great Explanation! Your videos are helping dev community a lot.
This video is really useful, thank you very much, some people mistakenly thought the dislike button was a download button :D
Thank you sir! I would have given up on the problem without this video.
Best explanation !
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
Awesome video Tushar sir
Thanks sir for your great effort... very simple and easy explanation.
That was very good explanation , cleared some of my doubts ! Thanks Tushar Sir :)
Great one!
Thank you so much sir.
Thanks for the explanation Tushar!
Superbly Amazing! Thanks mate :)
Weldone bruh Thanks
Thanks bhai, finally understood how it works. :D
Thank you. Very nice explanation.
Thank you so much! always the best!!!!
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!
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?
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)
Thanks a lot :D could you please add one of LCA By RMQ also.
Thank you bro!
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?
sweet and simple explanation , keep it up :D
good explanation
thanks a lot sir :)
thanks for the explanation.
The time complexity to query RMQ Sparse Table in your implementation is log*(n) (not to be confused with log(n), log*(n) is iterated logarithm) which can be reduced to O(1) by choosing 2 [L,R] values such that they cover all the nodes. Read this for more www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)
Nice explanation. But Plz use another marker
for range queries problems. which algorithm would be better?
great video sir :)
great as usual :D
Hi tushar! what is the logic behind putting index of minimum numbers in table , you could have directly put the minimum value direct in the table.
BTW nice video as always.
Is it only me who listen keyboard smashing sound when he write something on board
thank you very much
cout
Thank you!
Correct me If I'm wrong according to the sparse table being taught when i=4, j=0 in the first column, j will be 6 and i will be 7 and the min of both is 6 so the index of the 6 which is 1 should be returned right?
many thanks!
number of columns should be floor(log2(n))
why??
@@RomanReigns-ds8hs cp-algorithms.com/data_structures/sparse-table.html Read the Intuition part of the above link
can we use sparse table for max min range query in a 2d array(matrix)?
respect++
good
thanku sir
can you upload some questions related to it
wanted to give a double like to the video. but alas youtube restricted me two just one like.
does anyone know which problem in leetcode this is ?
G 17:23
is this MO's algo ??
Wouldn't it be more helpful if we store the elements directly..rather than their index
Exactly what I was wondering
Okay.. Got it.. The application of RMQ demands the storage of indices.. Because, usually, the minimum value is not just "Needed", it can also be updated.
Tushar bhai angrejo ki tarah English kyun bol rhe ho.....indian style English bol lo
Hi tushar, I think Segment tree takes O(n log(n)) space and time for pre processing. Not O(N)
the preprocessing time is o(nlogn)
This is O(N) just the same way a heap construction algorithm takes O(N).
@@madankumarrajan1028 Can you elaborate ? From my understanding, the heap construction algorithm time complexity is not very straight-forward to understand.
Also, segment tree should be O(nlogn) according to me, since we use divide and conquer and then sum (in case of Range sum queries) the two child node values.
first of all you should explain the logic or why we are doing something