It's HLD problem, you should have segment trees in every chain and every node of segment tree must be vectors which stores values in interval increasing order. but it is log ^ 3

Hi god_zoned,
I am able to come up with the following solution only right now.
Let decompose the tree using Heavy Light Decomposition. If you are not familiar with the technique check out this blog first.
Lets decompose the base array formed by the heavy light decomposition of tree in part of size each and also keep a linear table for each of these part say T_i where T_i, j denotes the number of elements in the i^th part with value  ≤  j. ( Assuming elements are  ≤ 10⁵ otherwise we can apply coordinate compression ). Now decompose all table T_i s in part as well. Note that this is done to improve the complexity of query operation by making update operation little costlier.
I meant to say, we can now update any element with complexity and query them with O(1) complexity.
Update: Update operation is very simple in this case as we just need to go to the desired block of size and update the element. In this case the point update will become a range update and this can be done with complexity.
Query: We know that we can traverse root to any node path with in at most chains ( due to heavy light decomposition ). Traverse all chains on the path from 1 to U and query the needed segment of a chain for the values less than x. This can be done in for each chain (as there can be atmost blocks in a chain and a block can be queried with O(1) time ) and therefore the overall complexity of the query part will be .

The above solution might be slower than what is expected. Anyone solution with better complexity and comments on the proposed solution are most welcome.

Auto comment: topic has been updated by Arunnsit (previous revision, new revision, compare).