Heavy Light Decomposition

help
1

I am not able to understand how segment tree is constructed . pls help

spoj : https://www.spoj.com/problems/QTREE/

https://blog.anudeep2011.com/heavy-light-decomposition/

2

Basically we store chains in segment tree and we query these chains effectively using HLD.
Also pls read comments in that section they will solve your doubt

2 Likes
3

I was recently going through all this stuff. Most probably you have read this to solve the Factor Tree problem. Apart from this, there is a single segment tree. You might be thinking why ??.

When we have chains different, so we should have a particular segment tree for a particular chain. You can implement that, but it will be a bit messy and you can be stuck in it.

So what we do, First of all, have look at basearray, it is jumbled up so that it has now contained nodes chainwise. The first chain comes first and so do their nodes then the second chain, and so on till the last node of the last chain.

Now you can implement the segment tree built on top of basearray for a range query. And the task remains is finding the range for which we have to query.

One thing I had noticed in Advanced Data Structures, they have their query and build functions so do HLD, the query_up function is that what I am talking about. It will provide you with the range. Query that range in the segment tree.

And Yeh, you had mastered one more Advanced data structure.

The beauty of HLD lies in the chains, handle it carefully.

2 Likes
4

Also if You like you can try this it is the easiest hld. If you can understand this it will be so much useful for queries on tree. I am saying this because hld implementation is rather complex or complicated.

1 Like
5

@hit12345 @rishabh3321
Can you help me with one doubt?
I’m trying to implement the hld which finds the sum of nodes along a path.
So the tree nodes have values 2,6,4,3,5 respectively and the edges are

1-2
1-3
2-4
2-5

My chains are like this:

chain 0 - 1,2,4
chain 1 - 5
chain 2 - 3

My segment tree looks like this when I try to print it -

0 20 8 12 2 6 3 9 0 0 0 0 0 0 5 4

I think its wrong since I don’t see sum 11(of chain 0). Can you help me in figuring out how will the correct segment-tree look like?

1 Like
6

why we are creating the segment tree.we don’t need to update the value for any node.
I think instead we should build prefix array for every chain which can be build in O(n) and gives ans in O(1) faster in both way compared to segment tree.

But still I am getting TLE :weary:

1 Like
7

i think correct segment tree should look like this -

0 20 11 9 8 3 5 4 2 6 0 0 0 0 0 0
2 Likes