You , are given an array of n elements and q queries . Both n and q can range upto 10^5 , and 1<=a[i] <= 10^9.
how to find / count all the elements less than a given element in each query .
queries are in the form of l , r , x where x is number and l and r are starting and ending indices.
Example: index 1 based
a[] = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }
q1 = 5 9 5
ans = 3 { 3 , 1 , 2}
q2 = 1 4 2
ans = 2 {2 , 2 }
The problem gives a feel of segment tree , but how to solve it using ST ?
any idea.