HLD segment/BIT

general
, ,
1

I read the QTREE6 editorial and honestly i have never solved any question of that type (related to tree queries)

But the editorial is mainly about HLD but i wanna know how do you store the given tree as segment tree/BIT to do the HLD on, i have no clue about this, so a most basic explanation/reference would be appreciated

Thanks

3 Likes
2

there is very nice editorials on BIT and segment tree given on topcoder…may this help u
ckeck this and this

2 Likes
3

First you decompose the tree into paths by the rule presented in the editorial. You need to maintain the father of a path(father[i]) and for each node the path that contains it (path[i]). Now you can use a vector (a[i]) obtained by concatening the previous stored paths and a second vector (pos[i]) where you store the position of a node in the paths vector(a[i]). At the same time you also need a vector (pstart[i]) to save the position of the first node in a path.

Let’s say that you want the minimum value between nodes x and y(presume that every node has a value). You start from y’s path and go from path to father[path] while the paths of x and y are not the same and check for the minimum in:

  • [pstart[path[y]],pos[y]] if path[x]!=path[y] ,after this step y=father[path[y]]
  • [pos[x],pos[y]] if path[x]==path[y].

The querys can be dealt with by using segment trees on a[i]. Try solving this problem first,because for QTREE6 you need to know lazy update on segment trees.

Complexity: log^2N (logN paths * logN query)

Example:
Given a tree with n nodes and m queries,and v[i]-value associated to node i,answer the queries:

  • 0 node value -change the value of node to value
  • 1 x y -find the minimum value between x and y

INPUT: n,m ;n lines v[1],v[2]…v[n];n-1 lines x y-edge between x and y;
OUTPUT:solution to 1 x y-type queries;

This is my source: http://ideone.com/HOeNbs

1 Like
4

i know BIT and segment tree, but i dont know how to use it to store a tree, that’s what I want know

5

Can you tell a problem from practice section where i could start learning this, maybe the most basic question you encountered where only HLD is required

6

http://acm.timus.ru/problem.aspx?space=1&num=1553

7

That is much appreciated, but since i have never done any question of this type, Is there any explanation for QTREE (spoj) somewhere

1 Like
8

Here are some more resources which I have found

http://apps.topcoder.com/forums/?module=Thread&threadID=796128&start=0&mc=8

http://apps.topcoder.com/forums/?module=Thread&threadID=727702&start=0&mc=5

http://wcipeg.com/wiki/Heavy-light_decomposition


Hope this will help…

2 Likes
9

thank you very much, appreciated