Heavy light decomposition: The hardest competitive programming algorithm
ฝัง
- เผยแพร่เมื่อ 19 ม.ค. 2025
- Heavy light decomposition is an advanced efficient range queries technique on trees. The algorithm uses least common ancestors and segment trees to answer queries.
We use binary lifting and segment trees as prerequisites for this video. Feel free to post your doubts or suggestions on the comments.
References:
HLD Problem Statement: www.spoj.com/p...
HLD blog: blog.anudeep20...
LCA using Binary Lifting: • Least Common Ancestor ...
Segment Trees: • Segment Tree - Range Q...
Code: ideone.com/EeDdrA
System Design Playlist: • System Design Playlist
You can follow me on:
LinkedIn: / gaurav-sen-56b6a941
Twitter: / gkcs_
Thanks a lot bro everytime waiting for heavy light decomposition from you.
This is the only place where I could find such an easy explanation to HLD Algorithm. I had learnt it the hard way.
Really concise and to the point without any rambling like most videos on this topic.
Absolutely fantastic. You explained this brilliantly. Very surprised I was actually able to get this with one watch-through. The pacing was great too.
Thank you.
Quality, Quality and more quality.....in every damn video on this channel.
Very nice tutorial. You put a lot of efforts creating this video. Thank you...
amandeep bhaiya rocksssss!!! making BIT MESRA proud!!
Respect and love. Keep making advance videos in the future for the ones in need like me.
Really well explained! Liked before watching it. Didn't regret it at all. :)
Thanks 😁
That intro was golden
Anudeep nekkanti!!, i am curious to know more about him, i had watched his few videos long back and then still in a question... What he's doing now!!
(His profile says he left Goole long back)
And the most interesting part is that you, akshay, anudeep, none of you are from IITs still so better than many.
And the best part is that you always mention your references & give them credits. :)
You're really great 👍
Amazing explanation Sir!
You made it so simple! Thanks brother.
Hey Gaurav, I really like your videos. I want to know how you make those videos. I want to start a YT channel about teaching C/C++ but I am confused about all initial setup that needs to be done. Specifically, I want to know the following things:
1. I want to know which whiteboard are you using (type and size) and where did you get it? (I couldn't find any good ones on Amazon and don't have any whiteboard store in my city)
2. Are you using any special camera or is it just a phone camera?
3. What lights and microphone? Are you using any softlights?
4. Which software do you use to edit your videos?
I know there are a ton of content available regarding this but I really like your channel and wants to know what you use. I would really really appreciate your help. Thanks a ton!!
for this particular question why don't we use Euler tour and store sum from root, and segment tree in Euler tour.
basically what we can do:
1. store the distances and sums from the root to the node on the node.
1. three Euler tours, - 1st for distances. 2nd for sums, and third for node values itself.
create a segment tree on Euler tour of sums.
for first query.
just get lca from distance Euler tour and RMQ, and sum between two (a, b) can be done using in O(1) using sums.
time complexity O(1) or O(logn)
for second query.
just update the values in the subtree of sums Euler tour.
time complexity O(logn)
P.S. my explanation is horrible and you will only be able to understand if you know how to Euler tour, LCA from Euler tour and segment tree on Euler tour.
Around 8:22, should it not be the height of each sub tree, not the size? I reason that that should be more efficient since we want to maximize the size of each chain
8:46, yes, we want to attach as many nodes to any given segtree (greedily), so why use size of sub trees and not height?
I think it has to do with the worst case query time if we go down a node. Can't think of any other reason.
Maybe you'd like to benchmark this version with the standard one? I'd love to see the results!
excellent explanation.
keep doing the great work.
Very very very thankful to you!!
😁
We can use to binary lifting to up word traversal of a node
most awaited video
sir your code is giving TLE on spoj. U can check !!
Awesome video! What's the best way to support range updates? Just standard lazy propagation or is there something better?
Lazy propagation keeps it down to O(logN) per chain. That's good enough :)
This some amazing editing :
Why not just dsu , instead of dfs ,chain can be denoted by ultimate parent,and union by size will keep track of size
*Interesting stuff*..👍
Can you please make videos on design patterns in oops
[
Gaurav:
Memer>Programmer
lol;
Thank you!
😁
Awesome 👏
Doubt in the code...
Hey Gaurav,
In the code is subtree_size array getting updated in dfs function right? It gets incremented only by one for each node whereas it should get calculated from downwards and size of each child should be added na?
Trees everywhere trees , what the hell is this 😂
:joy exactly
DS class
Hi Gaurav, can you please suggest a good resource for DP on trees. TH-cam is not helping me that much
charlie got me! :)
Thank you!!! gaurav
best video
Updating value will not change the segment?
The segment tree will handle it in O(logN) time.
thankyou
Ah... There are link-cut trees also and they are a step harder to my mind.
Yes...😛
Idk why i am watching this..
Advanced algo? TH-cam? ---> Gaurav Sen
nice