I've never seen any better tutorial on advanced data structures than this series. It feels like the author is able to offer explanations that runs in O(lgN) time while the majority of other people's explanation run in O(N^2) time ! The succinctness of the narrative accompanied with clean animation/diagram makes this channel a true hidden gem of the internet. Thank you for providing such high quality brain dumps to all of us!
I don't understand why this channel has so less subscribers... It's video quality, animation quality is top notch infact better than many other top youtubers and what shall I say about the teaching quality, IT IS THE BEST OF ALL!!!!
Holy god of trees. You are so underrated, I don't understand how this channel never popped to the top. You have my respect for this beautiful implementation and I offer my sub in perpetuity.
Thank you for the warm words! I suppose to get better rankings I should be networking, sharing links, this and that... But this is only a hobby for me, so I stick to the parts that I actually enjoy doing =) Cheers!
My god, the voice is so soothing and also I felt like I was given a very high class treatment. Over that I was thanked for watching. Plus there was no sponsorships, no ads, nothing. Best channel.
Very nice video, but the simple algorithm only works for a perfect binary tree. The modifications necessary to make it work otherwise are explained in the article you linked in your implementation. You can see this easily if your array has 7 elements: the first element of the array will be indexed at 7 in the structure, but its parent node is at index 2 in the tree, so not only do you lose the ability to use the last bit to determine if it's a left or a right child, but you also cannot simply divide by 2 to reach your parent. This is not horrible, because you can just pad your array to make it a power of two and it is still much better than algorithms that use 4*n memory, but you should probably mention it so that people are not confused by it's not working for them :)
Hi, for anyone wondering about the query algorithm. I thought about this, and I believe the rationale is this: so by construction, a parent node i, has left node 2*i and right node 2*i + 1. Now, we ask for [l, r). The idea is to move the pointers so that they meet, while ascending the tree to achieve O(logn) time. So if the left pointer node is odd then its a right child, and since the parent node includes the evaluation of both childs-intervals (i.e. also includes interval 2*i) but the indexes of the interval-node 2*i are lower than 2*i + 1, we need evaluate the node 2*i+1 immediately and move to the right, i.e. not evaluate the parent, otherwise we would be evaluating at least index (l - 1) [0...l-1] [indexes of interval-node 2*i]. If the left pointer is an even node, then it still in the evaluation-query interval, so we can keep moving above the tree. Same logic applies for the right pointer, if the right pointer is odd, as the interval is exclusive, we need to move to the left immediately and evaluate the node-interval and go above the tree, otherwise we would be consider at least interval [r...]. That's why when left pointer is odd, you evaluate immediately (to avoid including left indexes of the query interval [...l-1]) and increase the pointer. While for the right pointer you move the pointer immediately (to avoid including right indexed of the query interval [r...]) and evaluate the interval. So the conditions and evaluations are more for correctness of the algorithm rather than optimization.
That's a very good explanation. Thank you for posting it. By the way, when I mentioned the optimization part, what I meant was that you could still evaluate both children and then move up to the parent. The algorithm would still function in log n time. It's just that, as you very well explained, the children that are on the inside of the interval are handled by the parent node anyway. So might as well just not even bother looking at them and go directly to the parent.
@@yasser_hussain That's a good suggestion, thank you. This particular video had quite a lot of relevant information. Personally, I like seeing source code - that often fills in the missing gaps for me. I have listed 3 main files in the description. I hope this helps!
Hi, For anyone who was confused by the odd only evaluation. Convert this as [from, to] both inclusive. Then now the evaluation order should be only odd places on left and only even places on right. This way evaluation will form a cross and terminate where from and to cross each other. Effectively evaluating only those node that will definitely be left out in our movements upward. Meaning ‘/‘ shape for From’s movement and ‘\’ shape for To movement, effectively meeting at /\.
Yeah, that's a good suggestion - would make the code a bit cleaner. But, at this point the cat is already out of the bag and, well, youtube does not allow editing videos. But I glad to hear you mention this because it means you really looked through the code =)
This is the second video from Stable sort I am watching today. I hope that you keep on creating such amazing videos. It's clean, precise and just long enough . Thank you!
Great presentation. I know I'm late to the party, but I have a nitpick. The animation for the 5,6 max (6:33) shows the final value of the from and to indices as 6 when it should be 7. Here's why - from and to get incremented to 13 and 14 respectively from is odd, so: max is recalculated to tree[from], or 1. from is incremented to 14 to is even, so nothing happens from and to are divided by 2, so they're both 7 the loop ends since from == to.
Amazing video. Thanks for the explanation. For anyone looking for 307. Range Sum Query - Mutable: int sumRange(int left, int right) { int sum = 0; left += n; right += n;
while(left >= 1; //divide by 2 but a little faster right >>= 1; } cout
Such great explanations with pictures and visualizations, i loved how you talked about the code implementation as well along with the theory, the best 8:46 seconds spent on a video in youtube.
Thanks for raising a question. The "from" parameter is inclusive while the "to" parameter is exclusive. Sorry, I should have been more clear about this in the video. The source code linked in the description, however, does make this explicit. So when calling max(5, 6), the range is restricted to just one item at index 5, which is 1 in the example. I hope this makes sense!
@@stablesort Yeah, I see. It was raised due to an interview question leetcode.com/problems/range-sum-query-mutable/solution/ where _Approach 3: Segment Tree => 3. Range Sum Query => sumRange_ is almost the same except that it checks if the right (to) is even rather than odd. But it works as [ ] , not [ ) . Now it's clear
Great video! Very clear explanation of segment tree! By the way, around 5:30, when you are referring to the sum 1/2 + 1/4 + ..., you are using the term "geometrical sequence" -- the more appropriate mathematical term here is "geometrical series".
Yes, of course! Take a look at the Java source code linked in the description section ( bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java ). The update() method parameters are: index to the original array and the new value to be saved off.
@@stablesort Yes, but your update function can only update one index at a time. My question was about range updates, i.e updating multiple indexes in one go. To be more clear, your update function handles point updates, I'd like to know if it can be extended to handle range updates (something like "void update(int from, int to, int value)" )
Sorry for the late reply. Somehow youtube flagged my own reply as spam just because I had a link in it. That's an interesting question. I am assuming that you are referring to making updates in less than O(m log n), where m=to-from (otherwise, just calling update() method m times would do the job). From what I could tell, this can't be done for the general case, in which to/from could be any valid range, while segment tree uses any valid associative operation, such as min/max. But there is one special case that does allow for updates in O(log n), regardless of the to/from parameters. This works if the objective is to toggle boolean values in the range from/to, or some variant of that idea that can get way with just making two update(...) calls. I posted a video on this topic (that none watched) here: th-cam.com/video/oAR_EYd8im0/w-d-xo.html There a Fenwick tree is used, but a Segment Tree would work just as well. What do you think?
It is on my "to do list" =) I just want to fist cover a few more introductory tutorials on trees, such as the KD-trees and vantag-point-trees. And then add more complexity with lazy propagation, as you suggest.
I have seen many times different explanations (actually in three different languages) and this is the best I've seen so far. I am not certain if this is because I had some background knowledge, but this will be seen many times by my own students. Great (by all means) video and explanation. This is a very useful data structure in competitive programming as well, and until now I really get it. ¿Are you thinking in making a lazy propagation video?
wow, clearly explained the implementation of the segment tree, also the code you shared with us are very neat! thanks a lot! *hint, in the segment code, the index starts at 1 instead of 0 :)
You're very welcome! Yes, the value at index 0 is not used at all. Also, keep in mind that the "from" index in query(from, to) is inclusive while the "to" is exclusive.
I think if there are 5 elements, the method to build tree bottom-up doesn't work. To be specific, [1,2,3,4,5], the new array will look like [_,_,_,_,_,1,2,3,4,5] at first and then [_,_,_,5,9,1,2,3,4,5] the next should be [_,_,10,5,9,1,2,3,4,5] , but 10 is the sum of 9 and 1 which are from index - 0,3,4, which doesn't make any sense. Let me know if I am missing something.
Thanks for your question. I ran the code just now (source code in java: bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTree.java ) and the resulting "tree" for input [1, 2, 3, 4, 5] ends up being [null, 15, 10, 5, 9, 1, 2, 3, 4, 5]. That is, assuming segment tree uses addition for its binary operation. It may seem a little strange, as you pointed out, but the important thing is that the query() method is still able to reconstruct the correct values. Try it out yourself - query(0, 5)=15, query(1, 5)=9, query(0,4)=10, etc. it all checks out =)
@@stablesort yes, there is almost no tutorial which teaches to make a suffix array from a string. Discussion usually starts from matching techniques using it 😭
I really like the way you explain. What guarantees that the to and from will not overlap the range they cover? Because of idempotence of the max operation, overlapping would not hurt in your example. Should we must use a top-down (segment) solution or a fenwick tree for rangesum?
Thanks for the posting a question. Either of the data structures would work for range sum. Max operation does not work on Fenwick Trees. By the way, if you haven't seen already, check out Fenwick Tree tutorial here: th-cam.com/video/uSFzHCZ4E-8/w-d-xo.html
Nice video. For querying the segment tree you mention "if the index is even then its the left child node, we don't need to bother reading it since we'll get another chance at doing it on the next level up" why this is not the case for the right child? It kinda seemed to me that same argument could be made. Can you please explain further the "if(from & 1) result (+) = tree[from++] if(to & 1) result (+)= tree[--to]" logic? If it's an optimization, would the algorithm still work without those "if" conditions? Thanks in advance! [ (+) = binary associative operator, where a neutral element exists]
I could not understand what's the reason behind from++ and to-- when they are odd, could you please clarify? Without them we would just go to the parent and stop when node range is outside the given range
Hello, I understand how this explanation of odd from / to works for your example where the original input array is even in size. That is cause the if I am searching from O to 3 then it would get padded by n (8 here). But how will it work for when the input array is odd length say [6,10,5,2,7,1,0] then the segment array would be [ _, 10, 10, 6, 10 ,7 , 1, 6,10,5,2,7,1,0] and hence odd would be the left child, wouldn't it? Please let me know if I am mistaken? Thanks
Thanks for raising a question. Your segment array looks correct but I am not sure if I fully understand what you mean. Are you talking about the optimization in the query function that does the comparison only if both 'from' and 'to' indexes are odd? If so, this is in reference to the indexes of the segment array, not the original input array. In the segment array, if the index is even, then it's the left child node. We don't need to bother reading it since we'll get another chance at doing it on the next level up. I hope this helps but let me know if I misunderstood something. Cheers!
@@stablesort Yes I meant in the Segment array. What I meant is if the original array is getting right shifted by n (in the System.arraycopy step), then n itself being odd / even will determine whether the odd in the segment tree means right child.
@@RaoVenu Well, the odd/even check is only an optimization. You could implement it without it and compare every single pair. Have you checked out the source code? It may make more sense there (it's better commented). Here is the link: bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java
What if I wanted to make a generic segment tree where I can pass a key function like min, max, sum, multiply, etc? Cause this is only working fine for min/max type segment trees. Is there any possible way to accomplish the above?
the construction of the tree will fail if there are 5 nodes. Would you please that? for example n = 5, new array range from 0-9. we start looping down from index 4. 4 = index 8 + index 9, 3 = index 6 + index 7, and now index 2 = index 4 + index 5. but index 5 is the last left leave node while index 4 in the very right second level node. The logic completely breaks down here.
Excellent question and I am happy to see that you are really digging deep into this! When the tree was being constructed, the left child node was compared to the right child node and the winner was saved as the parent node. For example, left child = index 14, right child = index 15. The max of tree[14] and tree[15] was written into tree[7]. So if the "to" range, the right boundary, includes tree[15], then you don't have to examine tree[14]. Wait till the next iteration of the loop and just check tree[7]. So this is just an optimization, but I have to say that when I first realized this, it put a smile on my face =) I hope this helps but let me know if you'd like me to clarify this further.
@@stablesort but is it always correct? what if i need to find the max between index 0 to 1 in your example..adding it with n gives "from" = 8 and "to" = 9... now "from" is even so we skip it but "to" is odd so we do "to"-- which gives us max = tree[8] which is 6 but the max in range 0 to 1 is 10. I think the loop should run from while(from
Ahh, but there is a subtle detail - the input parameters to max(from, to) are such that 'from' is inclusive while 'to' is exclusive. So if you want to find the max from 0 to 1, then call max(0, 2). I suppose the video should have made it clear. It's just that, the function already took 21 lines of code so then to fit the comments in, I'd have to make the font smaller, making the video harder to follow... These are the kinds of things I have to balance out. The source code, however, does have it explicitly stated (line 59): bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java So I think we are good, but please let me know if you find any discrepancies =)
Could you explain more why we only need to evaluate only on odd indices? (7:18). How can we make the algorithm work without this trick? Also, I don't quite get the rationale behind only evaluating odd indices: The code is basically saying: if (from is odd) { // evaluate // make 'from' even } if (to is odd) { // make 'to' even // evaluate } therefore, for the case when 'to' is odd, aren't we evaluate nodes with even indices?
Good question. This is just an optimization. It works because if the index is even, then it's the left child node. We don't need to bother reading it since we'll get another chance at doing it on the next level up. It helps to have a picture of a tree representation of it and the flat array at the same time. Looking at it from a different angle, if the index is odd (suppose it's the 'from' node), the node must be the right child of its parent, so then interval includes node 'from' but doesn't include its parent. So here we must go in and do the comparison. I hope this helps but let me know if you aren't clear! There is also source code linked in the description.
@@user-ve1hm8bk7s Thanks for posting a question. The "from" parameter to the function is inclusive, while the "to" parameter is exclusive. So it's like [1, 3). I should have mentioned this in the video as a lot of people ask about it. But the source code (linked in the description) does state that explicitly. I hope this helps.
Great video!! Can anyone here help me with a confusion? The explanation says that we need to go up the tree in order to find the maximum in the range but what when the node is odd, the parent could represent the maximum because of the values outside the specified range! like in this example imagine the value after 7 is 1000 and not 1! then the value of the parent would be 1000 and therefore the algorithm would return 1000? I know I am doing it wrong but can't see why
@MrAbmishra, note that the query function "from" parameter is inclusive while the "to" parameter is exclusive (which follows Java's typical convention). If you keep that in mind, I think you'll agree that the code is correct ☺
This channel is highly underrated. More people need to know about this. Thank you very much, sir.
Thanks, I do appreciate your positive comments. Hopefully the good word will spread =)
@@stablesort You have a real gift for teaching concepts. Thank you.
I've never seen any better tutorial on advanced data structures than this series. It feels like the author is able to offer explanations that runs in O(lgN) time while the majority of other people's explanation run in O(N^2) time ! The succinctness of the narrative accompanied with clean animation/diagram makes this channel a true hidden gem of the internet. Thank you for providing such high quality brain dumps to all of us!
Thank you for such a wonderful compliment! As a fellow coder, I appreciate the 0(lnN) analogy =)
I don't understand why this channel has so less subscribers... It's video quality, animation quality is top notch infact better than many other top youtubers and what shall I say about the teaching quality, IT IS THE BEST OF ALL!!!!
Holy god of trees. You are so underrated, I don't understand how this channel never popped to the top. You have my respect for this beautiful implementation and I offer my sub in perpetuity.
Thank you for the warm words! I suppose to get better rankings I should be networking, sharing links, this and that... But this is only a hobby for me, so I stick to the parts that I actually enjoy doing =) Cheers!
My god, the voice is so soothing and also I felt like I was given a very high class treatment. Over that I was thanked for watching. Plus there was no sponsorships, no ads, nothing. Best channel.
Very nice video, but the simple algorithm only works for a perfect binary tree. The modifications necessary to make it work otherwise are explained in the article you linked in your implementation. You can see this easily if your array has 7 elements: the first element of the array will be indexed at 7 in the structure, but its parent node is at index 2 in the tree, so not only do you lose the ability to use the last bit to determine if it's a left or a right child, but you also cannot simply divide by 2 to reach your parent.
This is not horrible, because you can just pad your array to make it a power of two and it is still much better than algorithms that use 4*n memory, but you should probably mention it so that people are not confused by it's not working for them :)
Hi, for anyone wondering about the query algorithm.
I thought about this, and I believe the rationale is this: so by construction, a parent node i, has left node 2*i and right node 2*i + 1.
Now, we ask for [l, r). The idea is to move the pointers so that they meet, while ascending the tree to achieve O(logn) time.
So if the left pointer node is odd then its a right child, and since the parent node includes the evaluation of both childs-intervals (i.e. also includes interval 2*i) but the indexes of the interval-node 2*i are lower than 2*i + 1, we need evaluate the node 2*i+1 immediately and move to the right, i.e. not evaluate the parent, otherwise we would be evaluating at least index (l - 1) [0...l-1] [indexes of interval-node 2*i]. If the left pointer is an even node, then it still in the evaluation-query interval, so we can keep moving above the tree.
Same logic applies for the right pointer, if the right pointer is odd, as the interval is exclusive, we need to move to the left immediately and evaluate the node-interval and go above the tree, otherwise we would be consider at least interval [r...].
That's why when left pointer is odd, you evaluate immediately (to avoid including left indexes of the query interval [...l-1]) and increase the pointer.
While for the right pointer you move the pointer immediately (to avoid including right indexed of the query interval [r...]) and evaluate the interval.
So the conditions and evaluations are more for correctness of the algorithm rather than optimization.
That's a very good explanation. Thank you for posting it. By the way, when I mentioned the optimization part, what I meant was that you could still evaluate both children and then move up to the parent. The algorithm would still function in log n time. It's just that, as you very well explained, the children that are on the inside of the interval are handled by the parent node anyway. So might as well just not even bother looking at them and go directly to the parent.
Your SegTree implementation is cleaner and nicer than most other implementations I found on the internet. Thanks!!
Thanks, I do appreciate you taking the time to leave a few positive words =)
@@stablesort Thank you very much for the response. May I also suggest that please share links/resources/books which you refer to make your content.
@@yasser_hussain That's a good suggestion, thank you. This particular video had quite a lot of relevant information. Personally, I like seeing source code - that often fills in the missing gaps for me. I have listed 3 main files in the description. I hope this helps!
@@stablesort Great! Can you may be also make a video on how to implement ranged updates on a segment tree.
@@yasser_hussain Will do! Thanks!
This is the most underrated channel I have ever seen, great explanation keep it up
Thanks for the encouragement! I do appreciate it =)
Hi, For anyone who was confused by the odd only evaluation.
Convert this as [from, to] both inclusive. Then now the evaluation order should be only odd places on left and only even places on right. This way evaluation will form a cross and terminate where from and to cross each other. Effectively evaluating only those node that will definitely be left out in our movements upward. Meaning ‘/‘ shape for From’s movement and ‘\’ shape for To movement, effectively meeting at /\.
Yeah, that's a good suggestion - would make the code a bit cleaner. But, at this point the cat is already out of the bag and, well, youtube does not allow editing videos. But I glad to hear you mention this because it means you really looked through the code =)
Can you determine the left/right child only by the parity of the index? What if the size isn't even like the one from the example?
Great explanaition and animations! Thank you for putting so much time and effort towards making the video, I really appriciate it!
Thanks a lot for this channel. I feel like i have found a hidden gem.
This is the second video from Stable sort I am watching today. I hope that you keep on creating such amazing videos. It's clean, precise and just long enough . Thank you!
Thanks for the words of encouragement!
Thanks Andre .. your videos and explanations are crystal clear! hope this channel gets more attention!
I appreciate the good words!
Great presentation.
I know I'm late to the party, but I have a nitpick. The animation for the 5,6 max (6:33) shows the final value of the from and to indices as 6 when it should be 7.
Here's why -
from and to get incremented to 13 and 14 respectively
from is odd, so:
max is recalculated to tree[from], or 1.
from is incremented to 14
to is even, so nothing happens
from and to are divided by 2, so they're both 7
the loop ends since from == to.
Amazing video. Thanks for the explanation.
For anyone looking for 307. Range Sum Query - Mutable:
int sumRange(int left, int right) {
int sum = 0;
left += n; right += n;
while(left >= 1; //divide by 2 but a little faster
right >>= 1;
}
cout
Such great explanations with pictures and visualizations, i loved how you talked about the code implementation as well along with the theory, the best 8:46 seconds spent on a video in youtube.
Damn...amazing tutorial and the easiest segment tree implementation I've ever seen..Please also make a video about Lazy Propagation.
Thanks for the compliment and thanks for suggesting a topic - Lazy Propagation is definitely on my to-do list =)
The quality of the videos is very high. Thank you!
Amazing video. So simple and easy to understand!
Great video! There's just one thing you haven't considered: 6:33 say tree[14] = 999, the result is still 1.
Thanks for raising a question. The "from" parameter is inclusive while the "to" parameter is exclusive. Sorry, I should have been more clear about this in the video. The source code linked in the description, however, does make this explicit. So when calling max(5, 6), the range is restricted to just one item at index 5, which is 1 in the example. I hope this makes sense!
@@stablesort Yeah, I see. It was raised due to an interview question leetcode.com/problems/range-sum-query-mutable/solution/ where
_Approach 3: Segment Tree => 3. Range Sum Query => sumRange_
is almost the same except that it checks if the right (to) is even rather than odd. But it works as [ ] , not [ ) . Now it's clear
@@sagidM Thanks for the link - that's a good article!
nice video! thanks for sharing knowledge
best explanation so far! yet least recognized
Thanks for leaving a good word
such a cool and calm explanation, thanks Sir !!
Great video! Very clear explanation of segment tree!
By the way, around 5:30, when you are referring to the sum 1/2 + 1/4 + ..., you are using the term "geometrical sequence" -- the more appropriate mathematical term here is "geometrical series".
Amazing tutorial ! Really liked how simple your implementation is. Can this approach be extended for range updates as well?
Yes, of course! Take a look at the Java source code linked in the description section ( bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java ). The update() method parameters are: index to the original array and the new value to be saved off.
@@stablesort Yes, but your update function can only update one index at a time. My question was about range updates, i.e updating multiple indexes in one go. To be more clear, your update function handles point updates, I'd like to know if it can be extended to handle range updates (something like "void update(int from, int to, int value)" )
Sorry for the late reply. Somehow youtube flagged my own reply as spam just because I had a link in it.
That's an interesting question. I am assuming that you are referring to making updates in less than O(m log n), where m=to-from (otherwise, just calling update() method m times would do the job).
From what I could tell, this can't be done for the general case, in which to/from could be any valid range, while segment tree uses any valid associative operation, such as min/max. But there is one special case that does allow for updates in O(log n), regardless of the to/from parameters. This works if the objective is to toggle boolean values in the range from/to, or some variant of that idea that can get way with just making two update(...) calls. I posted a video on this topic (that none watched) here:
th-cam.com/video/oAR_EYd8im0/w-d-xo.html
There a Fenwick tree is used, but a Segment Tree would work just as well. What do you think?
Great tutorial as always.Will you be making a video on lazy propagation as well?
It is on my "to do list" =) I just want to fist cover a few more introductory tutorials on trees, such as the KD-trees and vantag-point-trees. And then add more complexity with lazy propagation, as you suggest.
I have seen many times different explanations (actually in three different languages) and this is the best I've seen so far. I am not certain if this is because I had some background knowledge, but this will be seen many times by my own students. Great (by all means) video and explanation. This is a very useful data structure in competitive programming as well, and until now I really get it.
¿Are you thinking in making a lazy propagation video?
Glad it was helpful and thanks for the compliment! To answer your question - yes, lazy propagation is left for another episode =)
wow, clearly explained the implementation of the segment tree, also the code you shared with us are very neat! thanks a lot! *hint, in the segment code, the index starts at 1 instead of 0 :)
You're very welcome!
Yes, the value at index 0 is not used at all. Also, keep in mind that the "from" index in query(from, to) is inclusive while the "to" is exclusive.
Great video, thank you!
Thanks for dropping a compliment!
Amazing explanation, you are a god
Awesome channel. Thanks a lot. Keep up the good work. Will subscribe till end of time
Awesome, thank you!
I think if there are 5 elements, the method to build tree bottom-up doesn't work. To be specific, [1,2,3,4,5], the new array will look like [_,_,_,_,_,1,2,3,4,5] at first and then [_,_,_,5,9,1,2,3,4,5] the next should be [_,_,10,5,9,1,2,3,4,5] , but 10 is the sum of 9 and 1 which are from index - 0,3,4, which doesn't make any sense. Let me know if I am missing something.
Thanks for your question. I ran the code just now (source code in java: bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTree.java ) and the resulting "tree" for input [1, 2, 3, 4, 5] ends up being [null, 15, 10, 5, 9, 1, 2, 3, 4, 5]. That is, assuming segment tree uses addition for its binary operation. It may seem a little strange, as you pointed out, but the important thing is that the query() method is still able to reconstruct the correct values. Try it out yourself - query(0, 5)=15, query(1, 5)=9, query(0,4)=10, etc. it all checks out =)
thank you so much!BTW, I like these short video clips in the video hahaha
Great! I am glad to hear it =)
Hello sir, please can you explain how does query work for array with size being non power of 2?
Great channel !!!
Please cover Suffix array
Thanks for the compliment and thanks for a great suggestion. I was just reading about suffix array - definitely an interesting topic!
@@stablesort yes, there is almost no tutorial which teaches to make a suffix array from a string.
Discussion usually starts from matching techniques using it 😭
wow i learned something from this video
thanks for the explanation, this helped. But you should have mentioned that this tree's nodes cannot distinguish between left and right child easily.
I really like the way you explain. What guarantees that the to and from will not overlap the range they cover? Because of idempotence of the max operation, overlapping would not hurt in your example. Should we must use a top-down (segment) solution or a fenwick tree for rangesum?
Thanks for the posting a question. Either of the data structures would work for range sum. Max operation does not work on Fenwick Trees. By the way, if you haven't seen already, check out Fenwick Tree tutorial here:
th-cam.com/video/uSFzHCZ4E-8/w-d-xo.html
Gummy bear jumpscare got me
I hope there will be more video of C++ , thanks for the video :3
Haven't done any C++ in about 20 years 8-)
@@stablesort noooo :((
Thanks, very good quality of content!
Glad you enjoy it!
Great vid
beautifully explained - thank you!
Nice video.
For querying the segment tree you mention "if the index is even then its the left child node, we don't need to bother reading it since we'll get another chance at doing it on the next level up" why this is not the case for the right child? It kinda seemed to me that same argument could be made.
Can you please explain further the "if(from & 1) result (+) = tree[from++] if(to & 1) result (+)= tree[--to]" logic? If it's an optimization, would the algorithm still work without those "if" conditions?
Thanks in advance! [ (+) = binary associative operator, where a neutral element exists]
I just noticed that you already answered your own question. Thanks again for posting your comments!
I could not understand what's the reason behind from++ and to-- when they are odd, could you please clarify?
Without them we would just go to the parent and stop when node range is outside the given range
while (l
Hello, I understand how this explanation of odd from / to works for your example where the original input array is even in size. That is cause the if I am searching from O to 3 then it would get padded by n (8 here).
But how will it work for when the input array is odd length say [6,10,5,2,7,1,0] then the segment array would be [ _, 10, 10, 6, 10 ,7 , 1, 6,10,5,2,7,1,0] and hence odd would be the left child, wouldn't it?
Please let me know if I am mistaken?
Thanks
Thanks for raising a question. Your segment array looks correct but I am not sure if I fully understand what you mean. Are you talking about the optimization in the query function that does the comparison only if both 'from' and 'to' indexes are odd? If so, this is in reference to the indexes of the segment array, not the original input array. In the segment array, if the index is even, then it's the left child node. We don't need to bother reading it since we'll get another chance at doing it on the next level up.
I hope this helps but let me know if I misunderstood something. Cheers!
@@stablesort Yes I meant in the Segment array. What I meant is if the original array is getting right shifted by n (in the System.arraycopy step), then n itself being odd / even will determine whether the odd in the segment tree means right child.
@@RaoVenu Well, the odd/even check is only an optimization. You could implement it without it and compare every single pair.
Have you checked out the source code? It may make more sense there (it's better commented). Here is the link:
bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java
What if I wanted to make a generic segment tree where I can pass a key function like min, max, sum, multiply, etc? Cause this is only working fine for min/max type segment trees. Is there any possible way to accomplish the above?
Yes, of course - see the source code that does exactly what you are asking about (linked in the description)
Awesome thx so much! Nice trick with zero element is not populated!!!
Cool! Glad to hear it was helpful!
the construction of the tree will fail if there are 5 nodes. Would you please that? for example n = 5, new array range from 0-9. we start looping down from index 4. 4 = index 8 + index 9, 3 = index 6 + index 7, and now index 2 = index 4 + index 5. but index 5 is the last left leave node while index 4 in the very right second level node. The logic completely breaks down here.
What's your linkedin and how come you don't upload more often?
i'm absolutely in love with your videos.. but can you please elaborate why are we ignoring the left child nodes at 7:13 ?
Excellent question and I am happy to see that you are really digging deep into this!
When the tree was being constructed, the left child node was compared to the right child node and the winner was saved as the parent node. For example, left child = index 14, right child = index 15. The max of tree[14] and tree[15] was written into tree[7]. So if the "to" range, the right boundary, includes tree[15], then you don't have to examine tree[14]. Wait till the next iteration of the loop and just check tree[7].
So this is just an optimization, but I have to say that when I first realized this, it put a smile on my face =)
I hope this helps but let me know if you'd like me to clarify this further.
@@stablesort but is it always correct? what if i need to find the max between index 0 to 1 in your example..adding it with n gives "from" = 8 and "to" = 9... now "from" is even so we skip it but "to" is odd so we do "to"-- which gives us max = tree[8] which is 6 but the max in range 0 to 1 is 10. I think the loop should run from while(from
Ahh, but there is a subtle detail - the input parameters to max(from, to) are such that 'from' is inclusive while 'to' is exclusive. So if you want to find the max from 0 to 1, then call max(0, 2). I suppose the video should have made it clear. It's just that, the function already took 21 lines of code so then to fit the comments in, I'd have to make the font smaller, making the video harder to follow... These are the kinds of things I have to balance out. The source code, however, does have it explicitly stated (line 59):
bitbucket.org/StableSort/play/src/master/src/com/stablesort/segtree/SegmentTreeMax.java
So I think we are good, but please let me know if you find any discrepancies =)
@@stablesort oh ok...that makes everything clear now..its really a cool optimization 😄
7:57 line 12, "to" is the right child when its odd ONLY if the original nums lenth is even, not always the case though?
I think this method only works if you pre-fill the nums to 2^n length
if location 13 and 14 swapped then how will it work ?
Could you explain more why we only need to evaluate only on odd indices? (7:18). How can we make the algorithm work without this trick?
Also, I don't quite get the rationale behind only evaluating odd indices:
The code is basically saying:
if (from is odd) {
// evaluate
// make 'from' even
}
if (to is odd) {
// make 'to' even
// evaluate
}
therefore, for the case when 'to' is odd, aren't we evaluate nodes with even indices?
Good question. This is just an optimization. It works because if the index is even, then it's the left child node. We don't need to bother reading it since we'll get another chance at doing it on the next level up. It helps to have a picture of a tree representation of it and the flat array at the same time.
Looking at it from a different angle, if the index is odd (suppose it's the 'from' node), the node must be the right child of its parent, so then interval includes node 'from' but doesn't include its parent. So here we must go in and do the comparison. I hope this helps but let me know if you aren't clear! There is also source code linked in the description.
@@stablesortWhen i tested max(1,3) with arr[5,2,7,9], max(1,3) returned 7 not 9. I expected 9 but function max() returned 7.
@@user-ve1hm8bk7s Thanks for posting a question. The "from" parameter to the function is inclusive, while the "to" parameter is exclusive. So it's like [1, 3). I should have mentioned this in the video as a lot of people ask about it. But the source code (linked in the description) does state that explicitly. I hope this helps.
@@stablesort Thanks for correcting me.
Very nice content. :)
@@user-ve1hm8bk7s Cheers!
Great video!! Can anyone here help me with a confusion? The explanation says that we need to go up the tree in order to find the maximum in the range but what when the node is odd, the parent could represent the maximum because of the values outside the specified range! like in this example imagine the value after 7 is 1000 and not 1! then the value of the parent would be 1000 and therefore the algorithm would return 1000? I know I am doing it wrong but can't see why
Segment tree somewhat looks similar to Heap data structure.
4:14 so cute
I came looking for copper and i found gold.
Thanks for leaving a few good words =)
4:12
That actually scared me
Max query code is not correct.
@MrAbmishra, note that the query function "from" parameter is inclusive while the "to" parameter is exclusive (which follows Java's typical convention). If you keep that in mind, I think you'll agree that the code is correct ☺
@@stablesort ok, thank you for your reply
Miller Frank Jones Sandra Taylor Amy
4:12 i really scared
Bu adam Türk değilse ben de bir bok bilmiyorum
Makul tahmin, ama ben kısmen Ermeni ve kısmen Beyaz Rusya'lıyım.