Problem:

Given an array of n integers and q queries of the form: Q(L, R, x). For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".

There is no update operation.

Constraints:

• 1 ≤ n ≤ 1900000
• 1 ≤ q ≤ 10⁵

I know two ways:

1. Using SQRT decompostion: Partition the array in SQRT(n) blocks and Sort each block. Then for each query binary search(lower bound or upper bound) x in each block. If I use Square Root Decomposition, complexity will be O(q * sqrt(n) * logn), which is not so good for this constraints, I think.

2. Using segment tree: Store the sorted list of numbers in each node in the segment tree. Then for each query, binary search x at each required node.

Can you please suggest any better solution for this problem ?

Thanks in advance.