I did not encounter this problem anywhere, i just happened to be doing query problems and i thought about this problem. Most probably based on segment tree since its range query type of problem.

So, here's the problem: Given an array of numbers, let's say non-negative for now, we want queries of the type how many numbers are less than given k in the range (l,r). All the three numbers l,r and k are given in query.

How would i go about solving this using ST or BIT!! Also, i tried the approach of storing maximum on every node of ST but in the worst case i think the whole tree would be explored destroying the logN complexity.