A Technique to convert Tree to a Linear Array for efficient query processing

This discussion is not specific to this particular problem .

but this is useful in many problems …

here are the links to some more problems

http://codeforces.com/problemset/problem/383/C

http://codeforces.com/problemset/problem/341/D

and even more …

I decided to answer as it is my area of interest :stuck_out_tongue: .

First of all … We can use slower solution mentioned by you to solve this problem but this will certainly run out of time if the test data is prepared well …

You must be familiar with the Binary Indexed Tree data structure … I am assuming you know how to perform these two operation over the BIT .

  1. update a point or an index
  2. query a range for the sum

We can reduce our tree problem to the problem where we just need to use the above mentioned functions to handle the updates and queries over the tree .

So, how can we transform tree to an array, such as for a node x, all nodes from subtree of x to be a subarray of array?

The answer is yes. We can do this by properties of DFS search. Before reading on, make sure that you know what is discovery time and finish time in a DFS search. Let’s build 3 arrays now – discover[], representing nodes in order of their discover times (a node is as before in discover as it has a small discover time), begin[] = for a node, in which time it was discovered and end[] = what’s last time of a discovered node before this node finishes. For a subtree of x, all nodes in the subtree are nodes in discover from position begin[x] to end[x].

Example: suppose you have tree 1-5; 1-6; 6-7; 6-4; 4-2; 4-3

Discover is {1, 5, 6, 7, 4, 2, 3}.

begin is {1, 6, 7, 5, 2, 3, 4}.

end is {7, 6, 7, 7, 2, 7, 4}.

What’s subtree of node 6? elements of discover from position begin[6] to end[6]. In this case, from 3 to 7, so elements {6, 7, 4, 2, 3}. You can see it’s correct and take more examples if you want :slight_smile:

void dfs(int u,int lev=0){
 
	L[u]=lev;
	V[u]=true;
	in[u]=++cnt;	
	for(vector :: itr it=G[u].begin();it!=G[u].end();++it){
		if(!V[*it]){
			dfs(*it,lev+1);
		}
	}
	out[u]=cnt;	
}

Look at this fragment code carefully this is the only most beautiful trick which is used in this problem .

we are maintaining the IN time and OUT time for a given node. Now if you think carefully all the nodes which have their IN time in between the IN time and OUT time of some node U represents the subtree of node U . Read the above things so many times so that you are completely clear with the idea and my efforts does not go in vain :stuck_out_tongue: .

once you are clear with the above idea problem reduces to one array and the mentioned queries . here is the full code for this problem .

int n,q,c,x,y,i,cnt=0;
VI L,in,out,BIT,V;
VL arr;
vector G;
 
 
void update(int idx,int val){
	
	while(idx<=n){
		BIT[idx]+=val;
		idx+=(idx&(-idx));
	}
}
 
int query(int idx){
	int sum=0;	
	while(idx>0){
		sum+=BIT[idx];
		idx-=(idx&(-idx));
	}
	return sum;
}
 
void dfs(int u,int lev=0){
 
	L[u]=lev;
	V[u]=true;
	in[u]=++cnt;	
	for(vector :: itr it=G[u].begin();it!=G[u].end();++it){
		if(!V[*it]){
			dfs(*it,lev+1);
		}
	}
	out[u]=cnt;	
}
 
 
int main(){
 
	cin >> n >> q;
	G.resize(n+1);
	arr.resize(n+1);
	V.resize(n+1);
	L.resize(n+1);
	in.resize(n+1);
	out.resize(n+1);
	BIT.resize(n+1);	
	rep(i,1,n){
		cin >> x >> y;
		G[x].pb(y);
		G[y].pb(x);
	}
	rep(i,1,n+1)
		cin >> arr[i];
	dfs(1);
	rep(i,1,n+1){
		if(arr[i]==0)
			update(in[i],1);
	}
	while(q--){
 
		char ch;
		cin >> ch >> x;
		if(ch=='Q'){
			
			int ans=query(out[x]);
			ans-=query(in[x]-1);
			cout << ans <> y;
			if(arr[x]){
				arr[x]+=y;
				if(arr[x]==0){
					update(in[x],1);
				}
			}else{
				arr[x]+=y;
				if(arr[x]){
					update(in[x],-1);	
				}
			}		
		}
	}	
	return 0;
}

25 Likes

I request you guys to add more and more problems of this topic to this post .

thanks

A different approach:
1)Build a size array denoting size of the subtree.

2)Build a preOrder Traversal Array “id” of the tree.

3)Align the values of nodes according to the preOrder traversal in a new array “val”.

4)Now you have to build a seg.tree on the “val” array.

5)Make sure you keep the node_id->index mapping so that you dont have to search in the id array for the
value during query and updation.

6)Query from index(u) to index(u)+sz[u] in the segment tree.

7)Updation is self-understood.

For more details refer :: https://www.codechef.com/viewsolution/21629376

add more problem of similar kind to this list …

http://www.hackerearth.com/algoholic_1/algorithm/dragon-wars/ This problem recently asked in a contest by IIIT-A uses Dfs order property and a segment tree (not persistant) as used in spoj problem MKTHNUM.

1 Like

Great charizard .

I am not able to get your end[] array?? :frowning:
Any help??

Hey, I need help :frowning:

@khooni_khopri i will surely help you just wait for some more hours(little busy) .

:slight_smile: :slight_smile: :slight_smile: :slight_smile: :slight_smile:

1 Like