Can range queries of form (l,r,x) where the answer to the query is number of values less than x in range [l,r] of a given array be solved in O(logn) time online? There are no updates. Plz describe the solution if it exists. I know of the solution by merge sort tree which solves it in O((logn)^2).