Code for HLD and persistent segment tree

general
, , ,
1

Can someone provide well commented and nicely explained code for persistent seg tree and HLD using segment tree(maybe with some sample problem). I am unable to code it neatly and my implementation is extremely dirty(especially for persistent). Can someone post code which is neat and understandable at the same time? Anudeep Nekkanti’s blog post also has code which is not extremely clean. Maybe some explanation via comments would help.

1 Like
2

Here’s my HLD code :

 int decompose(int u,int head)
  {
   cpos[u]=clen[head]+1;// pos of u in its chain 1 is from top. 1 based indexing
   clen[head]++;// length of chain starting from head. is 0 initially
   chead[u]=head;// head of chain in which u is there

   pair<int,int> mx={-1,-1};// max subtree
   for(auto it:g[u])
   if(it!=p[u])mx=max(mx,make_pair(sub[it],it));

   if(mx.first!=-1)
   decompose(mx.second,head);// continue same chain

   for(auto it:g[u]) if(it!=p[u] and it!=mx.second)decompose(it,it);//other chains
  }

Chains are stored like vector< int > tree[N]; where tree[i] is seg tree of chain whose head is i. To build them you can just traverse each edge resize them if of size 0 and then call point updates on them.

Then query for QTREE is like :

 int query(int u,int v)
 {
    if(chead[u]==chead[v])
    return qry(chead[u],1,1,clen[chead[u]],cpos[v]+1,cpos[u]);
    return max(qry(chead[u],1,1,clen[chead[u]],1,cpos[u]),query(p[chead[u]],v));//p[] is parent
 }

Here qry(head,node,left,right,u,v) is segment tree query of chain with head head from u to v.
This queries for max edge length(each edge length is corresponded to weight of lower node in that edge) from u to v such that v is ancestor of u.

2 Likes
3

For HLD, if you still have problem, u can checkout anudeep’s blog :


Code’s link : https://github.com/anudeep2011/programming/blob/master/qtree.cpp