Thank you william from South Korea!! Please do not remove these awsome videos. It really helped me a lot and helping me now. You make complicated things easy. I thank you again.!!
Shoutout to William and folks who contributed to this fantastic video. That being said, it's really a bummer that we're missing a video about a segment tree. Fenwick tree and Sparse table have its own advantages to select as primary datastructures, but when you need a point update for RMQ, then we definitely need to turn our heads to a segment tree :( The fact that other online sources aren't as easy to consume knowledge as your video, it would be much appreciated if you could make one in future!
What's RMQ? Range Min Query (or Range Max Query)? William Fiset says Fenwick Tree Point Update runs in O(log2(n)). Not good enough? Does a Segment Tree runs faster than this? I'm yet to learn about Segment Trees Please reply
WOAH this is really awesome, I appreciate the hard work put behind creating such top-notch quality content. your explanation is amazing William, please do keep posting such video's.
This is pure gold William, thank you for such a great content. I've been struggling with an advanced problem in Hackerrank and your video series about trees just pointed me to the right direction. :D
You should really bring the volume for your voice up, either via directly speaking to microphone louder or post processing as I have you turned up to 100% and if the room isn't completely quiet I cant hear you. If i play a song off of youtube at 5% it drowns you out even when your at 100% . Other than that great videos!
It depends. Sparse tables are great for fast range queries (although you do need nlogn memory). However, as soon as you need to be able to do any kind of point update or range update a segment tree is a good choice.
may be im stupid, but im not quite understand the idea. white, blue, intervals, subintervals. feels like author explain it to himself. not all people understand this, if they not reading Knuth
In CascadingMinQuery(), for product example where we have to find product of all elements between [0,6]. In first iteration of for loop we will have [0, 0 + 2^2) in next iteration it will be [4, 4 + 2^2) which should be [4, 4 + 2^1) as discussed in product range query example. We will not be having the t[2][4] in sparse table. Then how to check that in the function
Hi Netional, I think 15:25 is ok. I'm using the "half closed interval" notation [a, b) where a is inclusive, but b is not. Maybe I should have been more clear about that. As an example, the interval [3, 6) would mean {3, 4, 5}, not {3, 4, 5, 6}, and [4, 5) would just be: {4}
No, If the array is not static we need to update the sparse table which will take O(NlogN) time so, instead, you can use Fenwick tree or Segment tree (which takes only O(logN) time)
William tu to devta nikla re! Awesome 🔥
Thank you william from South Korea!! Please do not remove these awsome videos. It really helped me a lot and helping me now. You make complicated things easy. I thank you again.!!
Shoutout to William and folks who contributed to this fantastic video.
That being said, it's really a bummer that we're missing a video about a segment tree. Fenwick tree and Sparse table have its own advantages to select as primary datastructures, but when you need a point update for RMQ, then we definitely need to turn our heads to a segment tree :( The fact that other online sources aren't as easy to consume knowledge as your video, it would be much appreciated if you could make one in future!
What's RMQ? Range Min Query (or Range Max Query)?
William Fiset says Fenwick Tree Point Update runs in O(log2(n)). Not good enough? Does a Segment Tree runs faster than this?
I'm yet to learn about Segment Trees
Please reply
In first 2-3 minute u realize ur at right place for ur concept... awesome video:)
WOAH this is really awesome, I appreciate the hard work put behind creating such top-notch quality content.
your explanation is amazing William, please do keep posting such video's.
This is pure gold William, thank you for such a great content. I've been struggling with an advanced problem in Hackerrank and your video series about trees just pointed me to the right direction. :D
Amazing explanation! I'm finally at peace with this concept 👌
at 13:03 the equation of len should be len = r - l + 1 since r > l.
Amazing explanantion, was really helpful, thank you to William and the other collaborators!
amazing presentation. I prefer first to watch some videos like these to grip the high-level idea and read the book to dive deeper.
at 12:58, it should be len = R - L + 1 = 11 - 1 + 1, or?
You should really bring the volume for your voice up, either via directly speaking to microphone louder or post processing as I have you turned up to 100% and if the room isn't completely quiet I cant hear you. If i play a song off of youtube at 5% it drowns you out even when your at 100% . Other than that great videos!
Fantastic video, concept well explained🎉🎉
Thanks for the video. Finally, there's a good tutorial on Sparse tables. In your opinion, would you choose Sparse table over Segment trees
It depends. Sparse tables are great for fast range queries (although you do need nlogn memory). However, as soon as you need to be able to do any kind of point update or range update a segment tree is a good choice.
19:35 What happens with i is odd, and i/2 is a non-integer index of array log2
why will i want to use a sparse table for functions without good overlap??
i can use segment tree...
Thank you William. How did you compute last row at 16:00 please? I see that first element should be 2*-6*-6= -12*-6 = 72, but you wrote -12, why?
I computed -12 from the row above it from the cells at (row 1, col 0) and (row 1 col 2) for 2 * -6 = -12.
Great video! Very clear and concise!
why i+(1
may be im stupid, but im not quite understand the idea. white, blue, intervals, subintervals. feels like author explain it to himself. not all people understand this, if they not reading Knuth
Thank you for the great explaination
Great explanation William . Can you post some videos on string matching algorithms also.
Didnt understand how the table was constructed at 9:27
very clear and concise!
Why not using idempotency instead of overlap friendly term
not everyone is a boomer like you
So, the time complexity is O(log(n)), and space complexity is O(n*log(n)) ?
Thank you for the explanation
In CascadingMinQuery(), for product example where we have to find product of all elements between [0,6]. In first iteration of for loop we will have [0, 0 + 2^2) in next iteration it will be [4, 4 + 2^2) which should be [4, 4 + 2^1) as discussed in product range query example.
We will not be having the t[2][4] in sparse table. Then how to check that in the function
Notice that the cascading query function starts with the largest interval which is a power of 2.
Got it my bad
Amazing video
Thanks for the great video. At 15:25 the last segment goes to 16. I think it's an error.
Hi Netional, I think 15:25 is ok. I'm using the "half closed interval" notation [a, b) where a is inclusive, but b is not. Maybe I should have been more clear about that. As an example, the interval [3, 6) would mean {3, 4, 5}, not {3, 4, 5, 6}, and [4, 5) would just be: {4}
@@WilliamFiset-videos ah, I understand.
ThankYou so much for this !!
What if the array is not static? Can we use sparse table?
No, If the array is not static we need to update the sparse table which will take O(NlogN) time so, instead, you can use Fenwick tree or Segment tree (which takes only O(logN) time)
wonderful
It's very helpful
Volume is very low!
ty!
Dude the volume is so low
Just Wow!
Thanks for the tutorial. Can you please make video on lca queries as well?
awesome
bro you saved my life :LOL:
this is the best
great