title: Count nodes bigger then root in each subtree of a given binary tree in O(n log n)
body: <p>We are given a tree with <code>n</code> nodes in form of a pointer to its root node, where each node contains a pointer to its parent, left child and right child, and also a key which is an integer. For each node <code>v</code> I want to add additional field <code>v.bigger</code> which should contain number of nodes with key bigger than <code>v.key</code>, that are in a subtree rooted at <code>v</code>. Adding such a field to all nodes of a tree should take <code>O(n log n)</code> time in total.</p>
  
  <p>I'm looking for any hints that would allow me to solve this problem. I tried several heuristics - for example when thinking about doing this problem in bottom-up manner, for a fixed node <code>v</code>, <code>v.left</code> and <code>v.right</code> could provide <code>v</code> with some kind of set (balanced BST?) with operation <code>bigger(x)</code>, which for a given <code>x</code> returns a number of elements bigger than <code>x</code> in that set in logarihmic time. The problem is, we would need to merge such sets in <code>O(log n)</code>, so this seems as a no-go, as I don't know any ordered set like data structure which supports quick merging.</p>
  
  <p>I also thought about top-down approach - a node <code>v</code> adds one to some <code>u.bigger</code> for some node <code>u</code> if and only if <code>u</code> lies on a simple path to the root and <code>u&lt;v</code>. So <code>v</code> could update all such <code>u</code>'s somehow, but I couldn't come up with any reasonable way of doing that...</p>
  
  <p>So, what is the right way of thinking about this problem?</p>