Sparse Table & RMQ (Range Minimum Query)

[@ayushgaba7089]

He's the best competitive programmer in my opinion. He devotes so much to the community. Thankyou errichto!

[@Thy_panda_king]

Totally agree 😁

[@utkarshdevgan6199]

This is the greatest tutorial I have ever seen, soo detailed and crystal clear!!!!!!

[@Errichto]

Thanks :)

[@vishnusingh4118]

This is a work of art and beauty! There are people who can do but can't teach. Then there are those who can maybe teach but can't do. Then there are legends, who can do both at a mediocre level. And then God said, "Let Errichto be". 🙌. You make complex stuff seem so mind-blowingly simple! Can't thank you enough!

[@Errichto]

I think you're exaggerating but still - thank you!

[@gsscala]

That's crazy bro

[@saikumarganganapalli5957]

The transition from logorithm to constant complexity for each query had put a smile. That was so cool.😎. Excellent explanation. Keep it going.

[@Errichto]

I agree that the transition is nice and satisfying.

[@loonshott]

Thanks for this amazing course. Your explanation is just in another level.

[@berfubuyukoz353]

Watching you is almost like having a 1-1 lecture with you. It's as if you are empathetic to what the learner could think of next, and you answer in the next second (or more accurately, YOU enable the learner think the right way). I get the same experience when reading the book of Martin Kleppmann. I believe this is sth you see only from great explainers. Anyway, just wanted to share. Thanks for all the effort you put through your videos Errichto!

[@magnuseifr]

c++ also has builtin function __lg for base-2 logs with integers. Nice and clear explanation (as always)!

[@Errichto]

Oh, right.

[@GGxEpsilon]

I think log2 does the same, doesnt it?

[@magnuseifr]

@@GGxEpsilon I think __lg belongs to the gcc compiler and is designed to work on integers (or long longs) specifically. log2 should have the same behaviour, but as Errichto mentions in the video: floating point values are scary to work with.

[@rajd7002]

Finally a video that perfectly explains the core concept. I was able to come up with log n approach before you explained and was so proud of myself. And then you dropped constant time which blew my mind. :D Thanks Errichto!

[@mrdude1084]

I was looking for sparse table tutorial. When I saw Errichto's video in the list, I knew I couldn't get any luckier.

[@nighteagle6297]

You are the best competitive programmer. Very thanks. I understood it very clearly. Thanks for spending a lot of time to explain us. Thank you Errichto!

[@sureshchaudhari4465]

Errichto this is so nice and simple explanation I read it in book but did not understand you are really nice at explaining

[@BrunoSouza-wy2et]

amazing dude, I've been following your videos for a year now and you are always improving the way u teach. thanks !

[@Errichto]

Let's hope that I will keep improving then :)

[@asifanwarsajid8332]

Read about sparse table 2 days back. I checked if you had made any video on it. And here it is. 💯

[@__agpatel__]

He is really great and down to earth person....always willing to do something good for community....👍👍👍

[@vietnguyenquoc4948]

You explain this beautifully, thank you so much Hopes you comeback with more explaining video

[@anshusingh2473]

today i am practice codeforces Div2 C problem but i am not able to solve efficiently and seen editorial sparse table algorithm is used then learn this from your lecture then simply solve and learn this concept smart way very thankful for you explanation

[@ayamtaken2580]

I don't understand anything you're saying, but your voice is so soothing like ASMR to me

[@vaibhavtiwari6540]

Lmao, simp.

[@farhan787]

Finally Errichto is back :)

[@gauravupreti9340]

Best Explanation, you made it so easy to understand. Please keep up the good work 😊

[@manjuender6286]

Woah explained so simple, seems like a complex math but it is not once you understand the intent behind thanks a lot for the video

[@joserenteria5899]

i love learning from Errichto more than my own profs

[@sourandbitter3062]

This is very cool. Eager to learn about the segment tree. I didn't know about this. There surely are good use cases for this algorithm. For sure segment trees, or a similar structure, are used in databases.

[@hitesh6856]

Video quality and explanation is soo good. Thank-you!!

[@kxb6098]

Clear, concise, and perfect explanation

[@anowlwithinternet9125]

You never dissappoint!

[@glaucoa.9214]

Erichto you are the best person in the world!

[@rishabhkalra9505]

that was indeed a really good explanation to sparse tables. Thank you for this video. :)

[@CrystalSergeant]

I love even more your recent videos

[@vwv.1d]

may you get all of what you want in life..i respect you

[@ashisharyan3028]

Thank,I just needed this perfect and Crystal clear explanation .Orz

[@coefficient1359]

Very nice explanation Errichto

[@iftekharfahim]

Please do some Videos on Data Structure. Your explanations are simple and precise.

[@mjKeszely]

Duma rozpiera, że rodak jest takim mózgiem :)

[@hiderr6805]

Dzięki za pomoc w przygotowaniu do Olimpiady Informatycznej Juniorów (:

[@houcyhoucy3486]

Excellent! Which whiteboard tool do you use to draw on on screen? It seems great.

[@sameerbamnaha2189]

Amazing tutorial!!! Really enjoyed it and learned a lot!

[@subarnodatta2181]

Wonderful video. Helped me a lot sir

[@ahmmedsakibnoman2849]

plz do segment tree.. waiting for a long time..

[@5590priyank]

Amazing tutorial, for so long I was not sure how queries take constant time and not logN time. I always thought we need to answer each queries such that we divide range into powers of 2... finally your tutorial solved that for me that we need to take largest power of 2 which fits in given range and check from L and R end point and hence it is O(1). thank you so much for clearing this :) Also this clears why we can't use sparse table for answering range sum queries in O(1) because we are using overlapping ranges, right?

[@atharvasalokhe5168]

Hello guys, I am errichto, is so cool to hear

[@Vikash_Art]

For computing "k" in the query function we can do k=floor(log2(len)) then we can have 2^k

[@AnkitJosh]

Thanks ☺️ , this lecture was really helpful.

[@userrand4900]

Is the condition in line 30, correct? It does not reflect m[i + (1

[@tripleaplusb2214]

Hi , can I know the name of program used to explain pls?

[@vineethkumar8132]

Wow! its so clear even a 5 year old IQ guy lile me understands , Thank you for the wonderful content Ericchto !

[@priceandpride]

The brain on this man

[@beaujamo]

Thank you! Got mine working now! Awesome tutorial!

[@i_am_wiz]

Won’t the time complexity for answering a single query still logN as we are computing log2(len) where len is R - L + 1 which in worst case is of the order (N). So won’t the time complexity be logN per query?

[@ejackkulation7377]

Thank you, Errichto.

[@josealejandrovaroncarreno1692]

the best youtuber

[@madhvansharma5917]

Can we use sparse table for sum queries if we use the method where we convert ranges to binary and add it like we do in binary lifting (query time = logN)?

[@MehbubulHasanAlQuvi]

Keep up these good tutorials. Thanks a lot

[@pavankumar-cy6mg]

why it is k

[@xiangli9588]

you are wrong

[@learning7517]

I agree that using log2(x) is something to be avoided generally, however, if x < 2^31, it is guaranteed that the result of (int)log2(x) will be the same of any the bit tricks, so it might be a good choice if it's faster to code.

[@manas_singh]

How do you find problems on SPOJ? It seems so difficult to find by tags.

[@plosslaw]

Amazing stuff, good explanation

[@therealcdubbb8040]

Can you have multiple overlapping intervals?

[@isma--]

Hey Errichto, one question, what do you use in order to write your notes, i think you use like a tablet or something

[@simonstrandgaard5503]

Great explanation.

[@siddharthmagadum16]

He's sooo clever. Thanks for the video

[@vali8924]

Very nice explanation

[@joshuawilson6907]

I got WA with this code on spoj, do you guys have any ideas?

[@GGxEpsilon]

Errichto orz ❤️

[@ankitvats3295]

What an explanation! op

[@nileshchandra6435]

Should have checked this out before, not knowing sparse tables cost me yesterday as the seg tree failed in time.

[@subarnodatta2181]

I don't know why people disliked this video.🤷‍♂️🤷‍♂️

[@QngTu1159]

Can someone explain me what is “1

[@leviackerman9882]

Search bitwise left shift and right shift on KZbin Also i think errichto has a video on bit manipulation where he explained left shift and right shift

[@leviackerman9882]

Here you go : kzbin.info/www/bejne/romufWyPd7yaebs

[@QngTu1159]

@@leviackerman9882 Tks u so much

[@apoorvmehra121]

It means 2 to the power k

[@rohitoze9359]

Line 27, shouldn't it be i

[@parashararamesh4252]

How would we handle updates?

[@Errichto]

You need a segment tree for that.

[@shivam6829]

Please make detailed videos on segment tree and it various applications( like, min , max, updating, sum, frequency of max frequent element in the asked range etc...)

[@kongzilla2897]

Nice!! Binary is always Beautiful :)

[@jakoolaboo]

Thank you for this great video BTW : Is the __builtin function O(1) or O(log) or what ??

[@hitesh6856]

It is O(number of bits), so it is essentially O(1)

[@Errichto]

@@hitesh6856 It's O(1) rather than O(number of bits). CPU doesn't need to iterate bits one by one, it does it faster just like other basic operations like addition.

[@hitesh6856]

​@@Errichto ohh. I didn't knew that. Thanks! big fan..!

[@jakoolaboo]

@@Errichto thx for answering

[@srishtikdutta8946]

Awesome!!

[@Dima-Teplov]

Many thanks!

[@shrikantpadhy6125]

Segment tree can also do the same right? So whats the advantage here?

[@mohansharma-pt6yk]

Time complexity becomes O(N+Q*logN) and improves space complexity too

[@skt7088]

@@mohansharma-pt6yk in segment tree time complexity is O(QlogN)?

[@apoorvmehra121]

Amazing👍🏽👍🏽

[@shaoxiongduan]

legend.

[@milepivo]

It would be nice if you covered CSES problemset. It has a lot of educational problems that are hard to solve if you don't know the right technique.

[@KuaisArts]

check out CPH. CSES is a supplementary problem set to that book. Good luck!

[@BGOPC]

2 year's in and still waiting for the segment tree video

[@darshankubavat1764]

Errichto can you please make a video on how to deal with burnouts we face while constant coding?

[@joshuawilson6907]

I can AC the cses problem but cant for the spoj :))

[@skullcode8856]

10:00 this was when I started thinking that sparse tables are clever.

[@rishabhpurwar4875]

You're amazing

[@Steve168xyz]

Thanks for this vid - i like your background - so the goal to the get the O(N*log((N) + Q) though N is increasing tremendously ?

[@Errichto]

It's O(N*log(N) + Q) so it makes a lot of sense if Q is huge.

[@nishant5249]

We can also solve this problem using sliding window concept in O(n) time

[@gnet888]

Thanks You

[@p4rzival127]

This reminds of Reversort in Codejam Quali

[@aakashvishwakarma4653]

💯💯💯

[@tihomirjovicicify]

awesome

[@anshusingh2473]

your balance bracket concept apply div2 B problem in contest get Accepted and my rank under 2500 thanks for you good job

[@Errichto]

:)

[@puneetgoel7416]

What balance bracket concept? Could u pls share the link of that video 🙏🙏

[@anshusingh2473]

kzbin.info/www/bejne/ppq3Zmuag7GDnsk

[@dhakad22klx]

Easily explained.

[@asdfinonebody4103]

good !

[@koushiksaigopalamalladi5994]

pls do video on disjoint set union

[@Shirolicious]

i dnno, this guy is godtier. I cannot compute. syntax error

[@shnerdz]

please do segment trees next

[@nisarggogate8952]

Hey in preprocessing part inner for loop should be for(i=0;i+(1

[@imRJD14]

what a sexy explanation

[@anonymoussloth6687]

I saw this somewhere to find largest power of 2 less than or equal to n: x=n While(x&(x-1)) x&=x-1; Now x will be the answer

[@shalinisingh8688]

❤

[@MehbubulHasanAlQuvi]

First View, Like and Comment