How to augment a rooted tree using a segment tree or Binary Indexed Tree(with regards to QTREE6 editorial)?

general
, ,
1

I’m unable to understand the QTREE6 editorial in DEC13 long and seem to be going nowhere as it hasn’t been explained in great detail from an implementation point of view. I’ve understood what operations are to be carried out regarding the query and update procedure.But I don’t know how to implement them using a segment tree or BIT.I understand these data structures and HLD after reading the topcoder tutorials but if somebody could explain using pseudo code how to augment it.It’ll be much appreciated.

2

for each heavy chain u hv to construct a separate segment tree or binary indexed tree…i hv done it by using BIT by numbering all the nodes in a heavy chain consecutively and then perform all the operations you can view my solution here… http://www.codechef.com/viewsolution/3133132
since i hv not used binary search to find the lowest same color node that’s y my sol is taking so much time but i am skipping the heavy chains which hv all the nodes of same color…

1 Like
3

finally got AC using binary search but no effect on time…it has increased rather http://www.codechef.com/viewsolution/3144838

4

Could you explain the variable names inv_idx,idx_node?

5

idx_node[i] tells which number hv been assigned to the node ‘i’ in a heavy chian to use in BIT. if node ‘i’ and ‘i+1’ are in same heavy chain and i=parent(i+1) then idx_node[i]=idx_node[i+1]-1.
and inv_idx[i] is the inverse of idx_node[i] that is inv_idx[i] tells which node hv been assigned to the number ‘i’.