Binary lifting: Dynamic Programming on Trees
Vložit
- čas přidán 7. 07. 2020
- In this video, I provide a crisp and clear explanation of the concept of binary lifting which can be used to find the lowest common ancestor of two nodes in O(logN) time complexity.
I will explain both the explanation and coding part in-depth.
Code: ideone.com/Cg3bZT
If you liked the explanation let me know in comments, share with your friends and if you haven't subscribed yet then please do subscribe :)
Enjoy watching!!
Super useful books for algo ds and programming fundamentals!
1. Introduction to Algorithms by Cormen: amzn.to/35AmQqu
2. The Algorithm Design Manual: amzn.to/2K9RGPq
3. Fundamentals of Data Structures in C++: amzn.to/2LCwIsN
4. Object-Oriented Programming by E Balagurusamy: amzn.to/2Xxmdtr
5. Head First Java: amzn.to/39kb44K
6. Cracking the coding interview: amzn.to/3iDOHLK
7. Database System concepts: amzn.to/3pisuFQ
8. Operating Systems: amzn.to/39fcmis
9. Discrete Mathematics: amzn.to/2MlgCE6
10. Compiler Design: amzn.to/3pkYvx2
Loved the way how u explain the problems by breaking them down and explaining it further. Thank you for such an amazing explanation.
Simple and on point explanation . Thank you!
20k subs congrats well explained need more tutorials on cses problem sets
Brilliant and simple way of explaining . Kudos !!!
Came here after watching multiple videos. Thanks !! Very clear explanation.
Very easy to grasp because of your approach.......
Thanks for the great video
I think after completing your dp on playlist , I'll be able to solve most problems.video was Super useful as usual .
you've explained it so well !!thank you so much :)
very clear explanation....finally got the concept right!
Wish you make a proper graph and tree series just like you did for dynamic programming. That was superb..
great explanation Sir!!
Best explanation found so far....
Great Content!! , Not many teach like this with help of question !!, May it soon cross 1Million Subs
very simple and clear explanation thanx a lot!!!!!!!!!
Bohot hi Tagda explaination .
No challenge For this explaination
This binary lifting concept is really awesome. Thanks for explaining it so nicely.
I know right!!
such a clear explanation.....👍👍
@Kartik Arora Is it possible to solve this problem without binary lifting? Like collect all the queries indexed at each node. Now run a dfs, push the nodes to the path vector from the parent to the current node. Once it reaches the leaf, when we are recurring back, for the current node, we can compute the solution by comparing if k is lesser than pushed nodes vector size. Then store the solution for that query indexed at current node, then remove the current node from the path vector.
Awesome Explanation
Awesome content!
curated approach niceee
😍😍😍
wonderful explanation
Great Explanation man
great content bhaiya . .
Great work
You are a legend man! Keep it up!
Thanks a lot man :)
Finally I got perfect playlist.
Thanks a lot kartik
You're Welcome Amrit :)
in love with ur content
Awesome explanation. Helps a lot.
Thankyou Shivam!!
Try solving LCA of two nodes in logN per query using this technique.
I'll soon upload a video on that too.
Awesome! Quite good explanation!
Thankyou Astha!!
Bhaiya which hardware and software tools do you use to draw on screen???
Finally a good video so that I can understand the concept 🙌🙌
Thanks Himanshu!
Awesome, Thanks a lot
Such a detailed explanation to understand the logic behind the concept as well as the code. Thanks a lot.
Welcome :)
tumi sotti i gawd chile didi .
london theke kobe ascho?
Amazing!
Great content just sometimes its difficult to hear, sound is little low
In the LCA question, if we have a small number of queries(let's say around 10), then is binary lifting helpful? I mean to say for small number of queries, isn't the simpler O(NQ) algorithm more efficient? (Considering the preprocessing time here is O(NlogN))
If number of queries are large, binary lifting is very helpful.
Upto 50 or 100 queries, you can be happy with the brute force and get similar runtime.
best content in only 21:38 min
great
what is tree array holding and and what is the loop for this tree array. and since tree[src] is just an int then what are we looping here
Bhai awesome video....keep on uploading videos on DP and trees:)
Thanks bhai :)
sure will add more problems soon :)
Can someone tell me why the power's is upper bound is 20? 18 should be fine right?
In Answer Query function control reaches end with no return value how to resolve this ?
In the function that actually calculates the kth ancestor node, do we have to start from the biggest possible jump and keep dividing it by 2 at each step? I think starting from jump = 1 and doubling it works just fine and it is just as fast. I think it all depends on the actual value of k. Great video, thanks!
I am not entirely sure whether the doubling thing will work as efficiently or not. maybe if you explain it in more detail we can try discussing the complexity. I suspect it would be logN*logN instead of logN.
@@AlgosWithKartik Suppose the ancestor node for both nodes is 31 levels up from both nodes. Using the "biggest jump first" approach that you re showing, you will end up performing these jumps (in this order): 16+8+4+2+1=31. Totally valid. What I am saying is that you could also start from the lowest jump (jump to a parent) and double the jump size at each step: 1+2+4+8+16=31. I may be wrong but it seems to me that the efficiency and time complexity would be the same? The doubling approach may not be as efficient for other cases, I am not sure.
It is not really a big deal, I've seen binary lifting implemented in these 2 ways.
@@aliaksandrhn1 the doubling approach will be slower for some other jump sizes. For example: jump = 2^30.
You'll end up doing 29+29 jumps(max jumps you will ever make in biggest jump first method is number of bits in an int i.e 32). Instead of just 1 jump.(I assume once you can't do a jump large enough you reset jumpsize to 1)
Although it's a bit hard to prove but I still feel that the approach will be logN*logN
Think about jump sizes as binary numbers and try putting a upper bound on the time Complexity.
In practice you'll find both approaches will work good enough so that's alright :)
2 x-1 + 2 x-1 = 2x works like magic!
Please make a playlist on Game theory...It is no where available on CZcams
Top knotch man
Was having trouble understanding the 'Binary Lifting'. Now I don't. Thanks!
That's great Ajul, happy to know :)
for(int child : tree[src])
{
if(child != par)
binary_lifting(child, src);
}
Why we are checking condition of child ! = par??
Please clear my doubt!!
its like after once you have calculated all the power two parents of the src, you want to do the same for its children, therefore we have used the check child!=par, because now we want to find only the binalry lifted parents of the chidren
please share link of code
I'll share it in a while.
UPD: added in description.
@@AlgosWithKartik thanks bhiya
when we are calling, binary_lifting(int src, int par)
{
up[src][0] = par;
}
with arguments (1,-1)
so up[1][0] will be -1 but it should be 1 itself na? please clear my doubt bhaiya
actually the root of the tree has no parent.
So I have used an invalid value for parent to represent this fact.
There are many ways to implement the same functionality.
@@AlgosWithKartik but if we had to find 0th ancestor of root node then this method will be incorrect na ?
@@mridulkumar786 0th ancestor of any node will be the node itself.
Up[node][0] represents the 2^0 th =1st ancestor of node.
Hope this helps!
Loved someone picked cses
Why are you using windows 7
Kya phayda itni binary lifting ka abhi bhi ancient windows version use krte ho.
explanation is nice but it would be great if you write the code instead of explaining the prewritten code..... baki sb changga si