I need to do perform a task want any suggestion of data structure or any possible algorithmic hint.
For a tree with nodes numbered 1 to n answer following query
Given a node ‘k’. Consider ‘k’ to be the root and count the number of nodes in the subtree of each of its its children greater than k.
I need to perform this query for each node from 1 to n.
I need to perform all n queries in less than O(n*n).