Segment Tree question

[[Iasi] georgepopoiu]

Hello, I recently remembered a problem statement that was something like this :

We have an array A of n integers and we need to answer the following type of queries. Q(l, r, p) means how many numbers from A[l..r] are less than p. The author mentioned that it can be done using a segment tree, but did not provide any further clarifications and I cannot wrap my head around it.

Any ideas/tips ?

Thanks in advance !

[MMMMMua.....]

You have to build a segment tree in this way.
That is, for every segment tree node, it stored a sorted sequence of it's interval(use vector to allocate memory dynamically).
Obviously, the space complexity is O(nlogn).
And, for every query, use binary search to find out how many numbers are smaller than p, while locating the query interval(just like a normal segment tree).
So the time complexity is O(n(logn)^2).
I'm not an English speaker, so just ignore any grammer mistakes.....