You can refer to @l_returns ’ code for implementation. The first point is typical Euler tour on a tree, and I feel 2nd and 3rd point are sufficiently explained. Whats not clear to you?
Well, it looks like that the s[] and e[] are storing values of timestamps ( s[node] storing the time when node was first discovered and e[node] stores the value of finishing time when each node of its subtree was fully discovered ), am I right about this time stamping thing ?
I understood @l_returns solution , but this “time stamping” operation is slightly different from what I’ve studied in my class.
Example : For this tree (given below in image) this should be the starting and finishing times represented by s/e (written in pencil) for each node …
but according to the implementation it is giving output as :-
S[] = 0 1 2 3 4 5 6
E[] = 6 3 2 3 6 5 6
As far as I remember, for each node, you need to the know number of nodes greater/smaller than this in its subtree. Also, you need to know for each node, the number of nodes greater/smaller than it in the whole tree except the subtree…
Okay I understood your doubt.
Yeah there are two ways
One is 2n (all nodes will be inserted twice) and one is n.
You can use either depending on application
Yes , I figured that out a few days ago but I was a little bit confused about this time stamping thing . Anyways thanks again , my problem is solved now …
We get the size of subtree of a node by e[node]-s[node]+1, which I understood. But this number of nodes smaller than node in the subtree of node (i.e. Ss value of node), how are we getting the values ? I understood the query function which calculates sum (which is actually sum of 1’s) from s[node] to e[node].
I printed the dp[x] (which is an array of pair<>) for input of 0-1; 0-3; 3-2; 3-4 .
The final answer is 3 which is perfectly fine. But node 3 has node 2 in its subtree which is smaller but in the output for node 3 the value is 3 0 (here 3 is the size of subtree which is correct and 0 is the number of nodes smaller than node 3 in its subtree). I think the output should be 3 1.
Also for node 2 the value of the second column should be 0 because there is no subtree under it (it’s a leaf node).
In the array, we know that the range [Start[i],End[i]] denotes the subtree of node i where Start[i] is the time when we entered the node and End[i] is the time when we exited the node.
Now, we iterate through the nodes from smallest to largest. For each node, we do the following-
Find the sum of values in range [Start[i],End[i]]
After finishing computation for this node, update the value at appropriate index to 1 and proceed to next greater node.
Since all values are either 0 (if node is larger and hence the value is not yet made 1), or 1 (this node is smaller and its value is updated already), we just do a range sum query to find number of elements smaller than i.
the appropriate index you are talking about is s[i] ???
To get the number of nodes smaller than a particular node in its subtree we just need to execute a range sum query with s[node] and e[node] as starting and ending query indices ?
Hey, I got that part … Thanks a lot for your help. I’m now very close to the solution.
So I’ve computed Ss (number of nodes smaller than the node in it’s subtree) and total number of nodes present in the subtree of that node for every node in the whole tree. Now, how do I calculate this Bv and Sv ?What is meant by this recycle the same method ?